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

2026-01-20 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

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

题意分析

在数组 arr 中统计长度恰好为 k 的连续子数组里，平均值大于等于 threshold 的有多少个。要的是个数，不是位置，也不是最大平均值。

「长度恰好为 k」是全题最强的信号：候选子数组一共只有 n - k + 1 个，而且相邻两个候选之间只差首尾各一个元素。这直接排除了「枚举左右端点」的必要，也排除了「按条件伸缩左端点」的必要——窗口宽度从头到尾是常数。

「平均值 ≥ 阈值」这个判定不需要真的做除法。因为 k 恒正，不等式 sum / k >= threshold 两边同乘 k 就是 sum >= k * threshold，全程只用整数加减乘。

约束：1 <= arr.length <= 10^5，1 <= arr[i] <= 10^4，1 <= k <= arr.length，0 <= threshold <= 10^4。规模要求线性或接近线性的算法。顺手核算一下数值范围：窗口和最大是 10^5 * 10^4 = 10^9，k * threshold 最大同样是 10^9，都在 int 的 2.1 * 10^9 之内，不需要 long。元素全为正这一点也值得记住，它意味着窗口和随窗口右移不会出现「加了反而变小」的反直觉情况。

边界：k == n 时只有一个候选窗口；k == 1 时退化成逐元素比较；答案可能是 0，也可能是 n - k + 1（全部合格）。

解法：定长滑动窗口

核心思路

暴力解是枚举每个起点 i，再花 $O(k)$ 把 arr[i..i+k-1] 加起来，总共 $O(nk)$。当 n = 10^5、k = 5 * 10^4 时是 $5 \times 10^9$ 次加法，必然超时。

瓶颈很清楚：相邻两个窗口共享了 k - 1 个元素，这部分和被反复重算。既然窗口从 [i-k+1, i-1+1] 移到下一格只是「右边进来一个、左边出去一个」，那就直接维护窗口和的增量：sum(i) = sum(i-1) + arr[i] - arr[i-k]。

于是整个算法只需要一个标量 sum 和一遍遍历。循环不变量是：当遍历到下标 i 且 i >= k - 1 时，sum 恰好等于 arr[i-k+1..i] 这 k 个元素之和，也就是以 i 为右端点的那个定长窗口的和。

维护这个不变量只需要两步，且顺序天然：先把 arr[i] 加进来（右端点前进），再在 i >= k 时把 arr[i-k] 减掉（左端点跟进）。i < k 时左边还没有元素需要移出，窗口正处在「攒够 k 个」的预热阶段。

判定则用预先算好的 target = k * threshold：sum >= target 就把答案加一。把除法消掉的好处不只是躲开浮点误差——它让整个判定链条里只剩整数运算，不必再论证 sum / k 的向下取整会不会影响 >= 的结果（本题 threshold 是整数，恰好等价；但只要阈值变成小数，整除写法立刻失效）。

这就是定长滑动窗口的标准形态：没有 while 收缩，只有一进一出。它和 209、3 那类变长窗口的模板必须区分开——变长窗口靠 while 把左端点推到合法为止，定长窗口的左端点由右端点唯一决定。

解题步骤

预计算 target = k * threshold：把「平均值 ≥ 阈值」翻译成「窗口和 ≥ target」，之后循环里不再出现除法。

初始化 sum = 0、answer = 0，用一个下标 i 表示当前窗口的右端点。

右端点入窗：循环体第一行 sum += arr[i]，无条件执行。

左端点出窗：if (i >= k) sum -= arr[i - k]。条件是 i >= k 而不是 i >= k - 1——当 i == k - 1 时窗口刚好凑满 k 个元素，还没有元素需要移出，而且 i - k 会是 -1，直接越界。

统计：if (i >= k - 1 && sum >= target) answer++。门槛是 i >= k - 1，因为第 k 个元素的下标是 k - 1，这一刻才出现第一个完整窗口。两个门槛差 1，正是「出窗比满窗晚一格」的体现。

返回 answer。

以 arr = [2, 2, 2, 2, 5, 5, 5, 8]、k = 3、threshold = 4 走一遍，target = 12。

i = 0：sum = 2；i < 3 不出窗；i < 2 不统计。

i = 1：sum = 4；同样跳过两步。

i = 2：sum = 6，窗口是 [2,2,2]；i < 3 不出窗；i >= 2 进入统计，6 < 12，不计。

i = 3：sum = 6 + 2 = 8，再减去 arr[0] = 2 得 6，窗口是 [2,2,2]；6 < 12，不计。

i = 4：sum = 6 + 5 = 11，减去 arr[1] = 2 得 9，窗口 [2,2,5]；9 < 12，不计。

i = 5：sum = 9 + 5 = 14，减去 arr[2] = 2 得 12，窗口 [2,5,5]；12 >= 12，answer = 1。注意这里是恰好相等的情形，平均值正好 4，题目要求「大于等于」，必须计入。

i = 6：sum = 12 + 5 = 17，减去 arr[3] = 2 得 15，窗口 [5,5,5]；15 >= 12，answer = 2。

i = 7：sum = 15 + 8 = 23，减去 arr[4] = 5 得 18，窗口 [5,5,8]；18 >= 12，answer = 3。

返回 3。可以核对：六个窗口的和依次是 6、6、9、12、15、18，达到 12 的有三个，与逐窗口暴力求和的结果一致。

代码实现

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        // 两边同乘 k，把「平均值 >= 阈值」变成纯整数判定。
        int target = k * threshold;
        int sum = 0;
        int answer = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            // i == k - 1 时窗口刚好凑满，还没有元素需要移出，此时 i - k 也会越界。
            if (i >= k) {
                sum -= arr[i - k];
            }
            // 第 k 个元素的下标是 k - 1，从这一刻起 sum 才是完整窗口的和。
            if (i >= k - 1 && sum >= target) {
                answer++;
            }
        }

        return answer;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    // 两边同乘 k，把「平均值 >= 阈值」变成纯整数判定。
    target := k * threshold
    sum := 0
    answer := 0

    for i := 0; i < len(arr); i++ {
        sum += arr[i]
        // i == k-1 时窗口刚好凑满，还没有元素需要移出，此时 i-k 也会越界。
        if i >= k {
            sum -= arr[i-k]
        }
        // 第 k 个元素的下标是 k-1，从这一刻起 sum 才是完整窗口的和。
        if i >= k-1 && sum >= target {
            answer++
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$。数组只被遍历一遍，每个元素恰好被加入窗口一次、移出窗口至多一次，循环体内全是常数次加减与比较，与 k 的大小无关。

空间复杂度：$O(1)$。只用了 target、sum、answer 三个标量。这里特意没有开前缀和数组——前缀和同样能做到 $O(n)$ 时间，但要多花 $O(n)$ 空间，定长窗口把它压成了常数。

关键点总结

定长窗口没有收缩循环：右端点每前进一格，左端点必然跟进一格，用 if 而不是 while。看到「长度恰好为 k」就该条件反射地写出「一进一出」的骨架。

两个门槛差 1：出窗用 i >= k，统计用 i >= k - 1。前者防的是 i - k 越界，后者定的是「第一个完整窗口何时出现」，把这两处的语义分清就不会写错。

用乘法消除除法：avg >= t 改写成 sum >= k * t，判定链条里只剩整数运算，省掉全部关于取整和浮点误差的讨论。这个改写在「平均值 / 比例 / 分数」类题目里通用。

动手前核算数值范围：窗口和与 k * threshold 都不超过 $10^9$，int 足够。面试时主动报一句「我算过不会溢出」，比事后被问住要好。

面试视角：这题本身不难，考官真正想看的是你能否清楚说出定长窗口与变长窗口的模板差异，以及为什么不需要 while。能顺手指出「前缀和也能做但要多 $O(n)$ 空间」是加分项。

易错点总结

出窗条件写成 i >= k - 1：arr = [2,2,2,2,5,5,5,8]、k = 3 时，i = 2 会执行 sum -= arr[-1]，Java 直接抛数组越界异常，Go 直接 panic。

统计条件写成 i >= k：第一个完整窗口（下标 0..k-1）被漏掉。arr = [11,13,17,23,29,31,7,5,2,3]、k = 3、threshold = 5 的正确答案是 6，漏掉首窗口后变成 5。

把统计写在出窗之前：此时 sum 里还留着即将被移出的 arr[i-k]，相当于拿长度 k+1 的和去比 k * threshold，合格窗口数被系统性高估。

判定写成 sum > target：平均值恰好等于阈值的窗口被排除。走查用例里 [2,5,5] 的和正好是 12，答案会从 3 掉到 2。

target 直接写成 threshold：把「平均值阈值」误当成「窗口和阈值」。同一个用例里六个窗口的和全都不小于 4，答案会变成 6（即 n - k + 1）而不是 3。

在循环里再套一层求和：每到一个右端点就重新累加 k 个元素，n = 10^5、k = 5 * 10^4 时约 $5 \times 10^9$ 次加法，直接超时。滑动窗口的全部价值就在于消掉这层内循环。

套用变长窗口模板：写成 while (sum < target) 收缩左端点，窗口长度不再固定为 k，统计出来的是任意长度的合法子数组数量，答案与题意完全不符。

k == arr.length 时误以为无窗口：有人会写 if (k >= n) return 0 之类的提前返回，但此时恰好存在一个完整窗口，arr = [4,4]、k = 2、threshold = 4 的正确答案是 1，会被错判成 0。

相似题目

题目	难度	考察点
643. 子数组最大平均数 I	简单	同样是定长窗口且同样用和代替平均，但求的是最大值而非计数
1456. 定长子串中元音的最大数目	中等	定长窗口里维护的是字符计数而不是数值和，进出窗时改成加减 0/1
1423. 可获得的最大点数	中等	取首尾共 `k` 张，需要先转化成「长度 `n-k` 的定长窗口最小和」才能套模板
1052. 爱生气的书店老板	中等	定长窗口求最大增益，窗口外的固定部分要单独累加再与窗口结果合并
239. 滑动窗口最大值	困难	同为定长窗口，但维护的是极值这种不可加量，必须换成单调队列
209. 长度最小的子数组	中等	变长窗口的对照组：长度是待求量，左端点要用 `while` 收缩到临界
930. 和相同的二元子数组	中等	长度不固定且要求「恰好等于」，用两次「不超过」相减或前缀和计数
560. 和为 K 的子数组	中等	元素可负导致窗口和不再单调，滑动窗口失效，必须改用前缀和哈希