leetcode 1343. 大小为 K 且平均值大于等于阈值的子数组数目

发表于 | 分类于 | 阅读次数
leetcode 数据题

leetcode 1343. 大小为 K 且平均值大于等于阈值的子数组数目

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

来源：力扣（LeetCode）
链接：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：此题所描述的子数字为连续的。

解：

定义长度为k的滑动窗口, Sum为滑动窗口之和, num为符合条件的子数组个数,（滑动窗口为逻辑上的，实际代码无需实现）

循环遍历arr，当遍历到 i 时，Sum的值为 减去窗口最前值，加上窗口最后值， 然后比较Sum 与 threshold*k 大小, 如果Sum 累加num.

定义初始条件：

k = 3, 滑动窗口为 [2, 2, 2], Sum = 6, num = 0
Sum > threshold*k num = 1 否则 num = 0

遍历arr, 起始为k, 因为当前 前三个数已经在窗口了，因此遍历初始是第四个值，即 arr[3]

i = 3: [2, 2, 2] Sum = 6 , num = 0
i = 4: [2, 2, 5] Sum = 9 , num = 0
i = 5: [2, 5, 5] Sum = 12 , num + 1
i = 6: [5, 5, 5] Sum = 15 , num + 1
i = 7: [5, 5, 8] Sum = 18 , num + 1

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def numOfSubarrays(self, arr, k, threshold):

        Sum = sum(arr[:k]) #获取滑动窗口之和
        num = 1 if Sum >= threshold*k else 0

        for i in range(k, len(arr)):
            Sum = Sum - arr[i - k] + arr[i]
            if Sum >= threshold*k:
                num += 1
        return num