LeetCode 1343. 大小为 K 且平均值大于等于阈值的子数组数目
题目描述
题意分析
统计长度恰好为
k、平均值不小于threshold的连续子数组数量。不同起点算不同子数组，即使它们的元素完全相同，也要分别计数。
解法：定长滑动窗口
核心思路
[!blue]
题目保证 $k>0$，所以平均值条件
sum / k >= threshold等价于sum >= k * threshold。先计算总和门槛target，之后只做整数比较，既不需要浮点数，也不会发生除法截断。相邻两个长度为 $k$ 的窗口共享中间 $k-1$ 项，只需加入新的右端、减去离开的左端，就能得到新窗口和。遍历到
i时先加上arr[i]；若i >= k，此时临时多出一项，减去arr[i - k]。更新后，sum始终是截至i的最近至多 $k$ 个元素之和。只有
i >= k - 1才形成完整窗口[i - k + 1, i]，此时满足门槛就将answer加一。每个合法窗口都有唯一的右端点，依次检查这些右端点便恰好覆盖全部 $n-k+1$ 个窗口，不重不漏。
解题步骤
- 预先计算总和门槛。
- 每步加入右端，下标达到 k 后移出 i−k。
- 从 i=k−1 的首个完整窗口开始检查。
- 扫描结束后返回累计数量。
代码实现
class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int target = k * threshold;
int sum = 0;
int answer = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
// 满窗之后才移出旧左端，移出的下标是 i 减 k。
if (i >= k) {
sum -= arr[i - k];
}
// 首个完整窗口从第 k 个元素形成，等于门槛也计数。
if (i >= k - 1 && sum >= target) {
answer++;
}
}
return answer;
}
}
func numOfSubarrays(arr []int, k int, threshold int) int {
target := k * threshold
sum := 0
answer := 0
for i := 0; i < len(arr); i++ {
sum += arr[i]
// 满窗之后才移出旧左端，移出的下标是 i 减 k。
if i >= k {
sum -= arr[i-k]
}
// 首个完整窗口从第 k 个元素形成，等于门槛也计数。
if i >= k-1 && sum >= target {
answer++
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素最多加入和移出窗口各一次。
- 空间复杂度：$O(1)$，不保存前缀数组。
关键点总结
[!green]
- 首次满窗与首次移出相差一个位置。
- 平均值恰好等于门槛也计入。
k = 1时逐个判断元素，k = n时只判断整个数组，都由同一循环覆盖。- 题面中 $n\le10^5$，元素和阈值不超过 $10^4$，窗口和及
k * threshold都不超过 $10^9$。
易错点总结
[!yellow]
- 统计放在移出之前，会用到临时 k+1 项之和。
- 把平均值门槛直接当和门槛，会放宽条件。
- k 等于数组长度时仍有一个窗口，不能提前返回零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 643. 子数组最大平均数 I | 简单 | 固定窗口求和相同，本题统计达到平均值阈值的窗口，原题只取最大平均值。 |
| 209. 长度最小的子数组 | 中等 | 本题窗口长度固定，可把平均值阈值乘k转成和阈值；原题窗口长度可变并求最短。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！