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

题意

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

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

题目链接：1343. 大小为 K 且平均值大于等于阈值的子数组数目

思路

这道题是固定长度滑动窗口。

窗口大小固定为 k，只需要维护当前窗口的元素和 sum：

入：右端元素 arr[i] 进入窗口，累加到 sum。
窗口未成形：当 i < k - 1 时，窗口长度还不够 k，直接继续。
更新答案：窗口长度达到 k 后，如果 sum / k >= threshold，说明当前窗口满足要求，答案 count++。
出：减去窗口最左侧元素，让窗口准备向右滑动。

也可以把判断条件写成 sum >= k * threshold，避免每次做除法。

代码

function numOfSubarrays(arr: number[], k: number, threshold: number): number {
    let sum = 0;
    let count = 0;
    for (let i = 0; i < arr.length; i++) {
        // 入
        sum += arr[i];
        if (i < k - 1) {
            continue;
        }
 
        // 更新
        if (sum / k >= threshold) {
            count++;
        }
 
        // 出
        let left = i - k + 1;
        sum -= arr[left];
    }
    return count;
};

复杂度

时间复杂度： $O (n)$ ，每个元素最多进入和离开窗口一次。
空间复杂度： $O (1)$ ，只维护窗口和与答案计数。

滑动窗口模板小结

固定窗口滑动窗口的一般套路：

for 右端 in 遍历:
    加入右端元素到窗口状态
 
    if 窗口未满:
        continue
 
    更新答案
 
    移除左端元素，左端右移