大小为 K 且平均值大于等于阈值的子数组数目（滑动窗口解法）

题目描述

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例：

输入：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 的值）。

提示：

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

题解

滑动窗口：加尾去头，逐次向后滑动，利用中间解。本质上是动态规划。

依题意，若窗口中数值总和大于 k*threshold 则符合要求。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:   
        n = len(arr)
        res = 0
        sum_win = sum(arr[:k-1]) 
        right = k - 1
        while right < n:
            sum_win += arr[right]
            if sum_win > k * threshold:
                res += 1
            left = right - (k - 1)
            sum_win -= arr[left]
            right += 1
        return res