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

🎯 问题描述（来源于LeetCode）

描述：给你一个整数数组 arr 和两个整数 k 和 threshold。请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
说明：

子数组是数组中连续的元素序列。
为了方便计算，我们将“平均值 $\ge$ 阈值”转化为“总和 $\ge$ 阈值 $\times$ 长度”，避免浮点数运算。
示例：
示例 1：

输入：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，均大于等于 4。

示例 2：

1
2
3

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：所有长度为 3 的子数组的平均值均大于 5。

💻 解题思路

思路1：定长滑动窗口

思路1：代码实现

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        count = 0          # 记录满足条件的子数组个数
        count_num = 0      # 记录当前窗口内元素的总和
        
        for i, num in enumerate(arr):
            # 1. 扩展窗口：将当前元素加入总和
            count_num += num
            
            # 计算当前窗口的左边界
            left = i - k + 1
            
            # 2. 窗口未形成：如果左边界小于0，说明元素不足k个，跳过判断
            if left < 0:
                continue
                
            # 3. 窗口已形成：判断总和是否满足条件 (sum >= threshold * k)
            if count_num >= threshold * k:
                count += 1
            
            # 4. 收缩窗口：移除最左边的元素，为下一次滑动做准备
            count_num -= arr[left]
            
        return count

思路1：📊 性能分析

提交结果

运行时间：51 ms66.40% 的用户
内存消耗：29.63 MB22.89% 的用户

复杂度验证

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是数组 arr 的长度。代码只对数组进行了一次线性遍历，每个元素最多被访问两次（一次加入窗口，一次移出窗口）。
空间复杂度： $O(1)$ $O (1)$
- 只使用了 count 和 count_num 等常数个变量，没有使用额外的数组或数据结构。

思考

去浮点化技巧：题目要求平均值，但直接计算平均值涉及除法和浮点数比较，容易产生精度误差。将条件 avg >= threshold 转化为 sum >= threshold * k 是处理此类问题的标准技巧。
滑动窗口的精髓：相比于暴力解法（双重循环，每次重新计算 $k$ 个数的和），滑动窗口通过维护一个累加和变量，利用“增量更新”的方式，将时间复杂度从 $O(N \times K)$ 优化到了 $O(N)$ 。