How do I optimize this problem using the sliding window pattern?

By maintaining a running sum of the current window, you can efficiently update the sum as the window slides across the array. This eliminates the need to recalculate sums from scratch.

What is the time complexity of this approach?

The time complexity is O(n) because we process each element exactly once while sliding the window. The space complexity is O(1), as we only need a few variables to track the sum and valid sub-arrays.

What edge cases should I consider for this problem?

Edge cases include when `k` is equal to the array length, when no sub-arrays meet the threshold, and when the array contains repeated values.

Can I use this approach for larger arrays?

Yes, the sliding window approach is highly efficient and works well even for arrays with lengths up to 100,000, as it reduces the time complexity to O(n).

How does the threshold affect the number of valid sub-arrays?

A higher threshold will reduce the number of valid sub-arrays, as fewer sub-arrays will meet the average condition. Conversely, a lower threshold may result in more valid sub-arrays.

#1343

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

给你一个整数数组 arr 和两个整数 k 和 threshold 。请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。示例 1：输入： arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 输出： 3 解释：子数组 [2,5,5],…

数组滑动窗口

题目描述

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

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

示例 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 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

提示：

1 <= arr.length <= 10⁵
1 <= arr[i] <= 10⁴
1 <= k <= arr.length
0 <= threshold <= 10⁴

lightbulb

解题思路

方法一：滑动窗口

不妨将 threshold 乘以 $k$ ，这样我们就可以直接比较窗口内的和与 threshold 的大小关系。

我们维护一个长度为 $k$ 的滑动窗口，每次计算窗口内的和 $s$ ，如果 $s$ 大于等于 threshold，则答案加一。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 arr 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        s = sum(arr[:k])
        ans = int(s >= threshold)
        for i in range(k, len(arr)):
            s += arr[i] - arr[i - k]
            ans += int(s >= threshold)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because we process each element once while sliding the window. Space complexity is O(1) since we only need variables to track the current sum and the count of valid sub-arrays, regardless of input size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate implement the sliding window approach efficiently?
question_mark
Does the candidate handle edge cases such as when `k` equals the array length?
question_mark
How well does the candidate explain their approach, especially with respect to avoiding recalculating sums repeatedly?

warning

常见陷阱

外企场景

error
Incorrectly recalculating the sum for every sub-array from scratch instead of updating it incrementally.
error
Missing edge cases like when the size of the sub-array `k` equals the array length.
error
Not properly handling the condition where no sub-arrays meet the threshold, leading to returning an incorrect count.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would this approach change if we need to track sub-arrays of variable sizes?
arrow_right_alt
What if instead of an average, the threshold were a sum condition?
arrow_right_alt
How could this solution be adapted for multidimensional arrays or matrices?

help

常见问题

外企场景

继续练习

#1423 可获得的最大点数 #1425 带限制的子序列和 #1248 统计「优美子数组」