LeetCode 643. 子数组最大平均数 I
目录
题目描述
题意分析
要什么：在数组中找出长度恰好为
k的连续子数组，使其平均值最大，返回这个最大平均值（浮点数，允许 $10^{-5}$ 的误差）。
约束透露的信号：长度被钉死为k，所有候选子数组的分母完全相同，于是「平均值最大」和「和最大」是同一个问题——先把除法丢掉，最后再补上。长度固定还意味着候选区间的左右端点是绑定的，右端点一确定左端点就唯一，这正是定长窗口能一遍扫完的根本原因。$n$ 到 $10^5$ 且元素可负，说明要线性算法且不能用「和越加越大」这类只对正数成立的直觉。
边界：k保证不超过n，所以至少存在一个合法窗口，不必处理无解；元素可为负，最大和可能是负数，答案初值必须取第一个真实窗口的和而不是 0；元素绝对值上限 $10^4$ 且k到 $10^5$，窗口和最大约 $10^9$，在int边缘，用 64 位更稳妥。
解法：滑动窗口维护有效区间
核心思路
暴力做法是枚举每个起点，再往后累加
k个元素求和，取最大值，时间 $O(nk)$，在 $n = k = 10^5$ 时是 $10^{10}$ 级，必然超时。
瓶颈很直白：相邻两个窗口[i, i+k-1]与[i+1, i+k]有k - 1个元素完全重合，暴力却把这部分反复加了一遍又一遍。
观察到窗口右移一格时，集合的变化只有两处：吐出最左边的nums[i-k]、吞入新的nums[i]。既然变化是 $O(1)$ 的，和的更新就该是 $O(1)$ 的。
由此得到要维护的不变量：每轮循环开始处理下标i时，sum恰好等于窗口[i-k, i-1]的元素和，maxSum是所有已经完整出现过的定长窗口和的最大值。整个算法就是让这条不变量在窗口右移时保持成立，最后把maxSum除以k还原成平均值。
解题步骤
- 先把
nums[0..k-1]累加成sum，并令maxSum = sum。为什么答案初值取第一个窗口而不是 0 或极小值：元素可以是负数，最大窗口和完全可能为负，用 0 当初值会返回一个根本不存在的窗口；用第一个真实窗口初始化既安全又省掉一次特判。- 从
i = k遍历到n - 1，每轮执行sum += nums[i] - nums[i - k]。为什么是i - k：当前窗口是[i-k+1, i]，上一个窗口是[i-k, i-1]，被挤出去的正是下标i - k；写成i - k + 1或i - k - 1都会让窗口长度悄悄变成k ± 1。- 每次更新完
sum后立刻比较并更新maxSum。为什么更新时机在加减之后：只有加减都做完，sum才代表一个长度恰为k的合法窗口；提前比较会把长度为k + 1的中间态误当成候选。- 返回
maxSum * 1.0 / k。为什么要显式转成浮点：maxSum和k都是整数，直接相除会做整数除法，把 12.75 截成 12；先乘 1.0（或在 Go 里两边都转float64）才能得到真实平均值。- 以
nums = [1, 12, -5, -6, 50, 3]、k = 4走一遍。初始化阶段累加前四个元素得sum = 1 + 12 - 5 - 6 = 2，maxSum = 2，此刻窗口是[1, 12, -5, -6]。i = 4：sum += nums[4] - nums[0] = 50 - 1，sum变 51，窗口滑到[12, -5, -6, 50]，51 大于 2，maxSum = 51。i = 5：sum += nums[5] - nums[1] = 3 - 12，sum变 42，窗口滑到[-5, -6, 50, 3]，42 不超过 51，maxSum保持 51。循环结束返回51 / 4 = 12.75。可以反向验证：窗口[12, -5, -6, 50]的和确实是 51，是三个候选窗口（2、51、42）里最大的。
代码实现
// 核心实现：滑动窗口维护有效区间，维护必要状态并避免重复处理。
class Solution {
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
long sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
long maxSum = sum;
for (int i = k; i < n; i++) {
sum += nums[i] - nums[i - k];
if (sum > maxSum) {
maxSum = sum;
}
}
return maxSum * 1.0 / k;
}
}
// 核心实现：滑动窗口维护有效区间，维护必要状态并避免重复处理。
func findMaxAverage(nums []int, k int) float64 {
sum := 0
for i := 0; i < k; i++ {
sum += nums[i]
}
maxSum := sum
for i := k; i < len(nums); i++ {
sum += nums[i] - nums[i-k]
if sum > maxSum {
maxSum = sum
}
}
return float64(maxSum) / float64(k)
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：初始化累加
k次，主循环走n - k轮且每轮只做一次加、一次减、一次比较，两段相加恰好是 $O(n)$，每个元素只被加入和移出窗口各一次。- 空间复杂度：$O(1)$。凭什么：只用了
sum、maxSum、i几个标量，没有前缀和数组也没有额外容器，窗口本身用两个下标隐式表示。
关键点总结
- 定长窗口的本质是增量维护：窗口右移时集合只变化常数个元素，因此任何「可加可减」的统计量（和、元音个数、字符频次）都能 $O(1)$ 更新，把 $O(nk)$ 降到 $O(n)$。
- 「最大平均值 + 长度固定」要第一时间转化成「最大和」。分母是常数时先约掉，能同时避免精度问题和不必要的浮点运算；一旦长度可变（如 644 题），这个转化就失效，必须换成二分答案。
- 极值初始化永远从真实存在的候选取，而不是从 0 或凭感觉的常数取。元素含负数时这一条会直接决定对错。
- 定长窗口和变长窗口是两套模板：定长的右指针每步必移、左指针跟着走，没有
while收缩；变长的才需要「不满足条件就收缩左边界」。面试里说错模板会被认为没分清题型。- 面试视角：这题写完只有五六行，真正的加分项是主动指出「整数除法陷阱」和「窗口和可能超
int」这两个细节，并说明为什么把除法留到最后一步做。
易错点总结
- 错误写法：
maxSum初始化为 0；用例nums = [-1, -2, -3]、k = 2→ 所有窗口和都是负数，返回 0 对应的 0.0，正确答案是-1.5。- 错误写法：返回
maxSum / k；用例nums = [1, 12, -5, -6, 50, 3]、k = 4→ 整数除法把51 / 4算成 12，返回 12.0，正确答案 12.75。- 错误写法：滑窗时写成
sum += nums[i] - nums[i - k + 1]；用例nums = [1, 2, 3, 4]、k = 2→i = 2时减掉的是nums[1] = 2之外的错误元素，窗口长度失控，返回值与任何真实窗口都对不上。- 错误写法：在减去左端元素之前就更新
maxSum；用例nums = [1, 2, 100, 1]、k = 2→ 中间态sum一度代表三个元素之和 103，被误记为最大值，返回 51.5，正确答案 51。- 错误写法：主循环从
i = k - 1或i = 0开始；用例nums = [5, 1, 1]、k = 2→ 从i = 0起会访问nums[-2]直接越界；从i = k - 1起会把第一个窗口重复计算一次并减错元素。- 错误写法：用
int存sum；用例k = 10^5且所有元素为 $10^4$ → 窗口和达到 $10^9$，再叠加中间的加减极易越过int上限，得到负数结果。- 错误写法：每轮重新遍历窗口内的
k个元素求和；用例n = k = 10^5→ 结果正确但退化到 $O(nk)$，直接超时，等于没做优化。- 错误写法：套用变长窗口模板，写
while (窗口长度 > k) 收缩；用例 任意输入 → 逻辑虽可能正确，但每次进入while都要判断，代码变长且极易在只需固定长度时误收缩到k - 1。- 错误写法：用
double累计窗口和以图省事；用例 长度 $10^5$ 的数组 → 浮点累加带来舍入误差，虽然本题误差容限宽松未必挂掉，但比较大小时可能因误差把两个真实相等的窗口判成不等，属于无谓的风险。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1456. 定长子串中元音的最大数目 | 中等 | 窗口内统计量从「和」换成「满足条件的字符个数」，增量更新方式相同 |
| 1052. 爱生气的书店老板 | 中等 | 需要先拆出固定收益，再用定长窗口最大化「额外挽回」的部分 |
| 1423. 可获得的最大点数 | 中等 | 取两端的问题要反向转化成「最小化中间定长窗口的和」 |
| 1151. 最少交换次数来组合所有的 1 | 中等 | 窗口长度由数组中 1 的总数动态确定，需要先扫一遍才知道 k
|