先回答一个不少刷题新手都问过的问题力扣上那道“子数组最大平均数 I”LeetCode 643标签是简单题但为什么很多人一上来就写错我见过不少人在评论区吐槽说自己用双重循环暴力解结果直接超时还有人用前缀和写出来了却被面试官追问“能不能不用额外空间”时卡住。这道题看似只是算平均数真正的考点其实是滑动窗口——你如果把它当数学题做十有八九要走弯路。这篇文章不打算只贴一份能过的代码我会把从题目理解、解题思路、多种写法、边界处理到同类拓展的完整链路都拆开讲一遍顺便把我实际刷题时踩过的坑和面试里被追问过的问题也一并列出来。适合刚接触滑动窗口的入门读者也适合准备面试想把这题吃透的人。1. 暴力解法的失败现场为什么双重循环会超时1.1 题目到底在问什么先看题面给定一个整数数组 nums 和一个整数 k找出该数组中长度为 k 的连续子数组并输出这些子数组里最大的平均值。比如 nums [1, 12, -5, -6, 50, 3], k 4所有长度为 4 的连续子数组有[1, 12, -5, -6]平均值 0.5[12, -5, -6, 50]平均值 12.75[-5, -6, 50, 3]平均值 10.5最大值是 12.75所以输出 12.75。注意题目说的是“连续子数组”不是“子序列”。连续意味着这些元素在原数组里必须一个挨着一个不能跳着选。这一点看起来像废话但真有人会忽略——我见过有人拿排序后的数组去算那就完全跑偏了因为排序会破坏元素间的相邻关系。1.2 大多数人第一反应的代码长什么样新手拿到这题最直接的想法是把所有长度为 k 的子数组全都枚举出来分别求和再除以 k取最大值。写成代码大概是这个样子public double findMaxAverage(int[] nums, int k) { double maxAvg -Double.MAX_VALUE; for (int i 0; i nums.length - k; i) { int sum 0; for (int j i; j i k; j) { sum nums[j]; } maxAvg Math.max(maxAvg, (double) sum / k); } return maxAvg; }这段代码逻辑上没问题结果也没错但时间复杂度是 O((n - k 1) * k)也就是约等于 O(n*k)。当 n 和 k 都很大时运行时间会急剧上升。比如 n 100000k 50000内层循环大约要执行 25 亿次加法这在力扣的评测环境里基本就是超时。1.3 暴力解法到底浪费在哪里暴力解法的浪费之处在于相邻的两个窗口之间有大量重复计算。第一个窗口覆盖 nums[0] 到 nums[3]第二个窗口覆盖 nums[1] 到 nums[4]。也就是说nums[1]、nums[2]、nums[3] 这三个元素被加了两次。窗口每向右移动一位实际上只有两个元素发生变化左边滑出去一个右边滑进来一个中间 k-1 个元素根本没必要重新加一遍。这就好比排队打饭你每次从队尾重新数一遍人数而不是记住上次的人数然后加减进出队伍的人——后者显然更快。这个观察就是滑动窗口思想的起点。2. 滑动窗口的推导过程从 O(k*n) 降到 O(n)2.1 窗口滑动的核心观察基于上面的分析我们只需要维护一个长度为 k 的“窗口”每次窗口右移时减去滑出窗口的元素加上滑入窗口的元素更新最大值这样一来每个元素最多被加入一次、移除一次整体时间复杂度降为 O(n)。用生活化的比喻你坐在一趟行驶的火车上透过窗户看外面的风景。火车每前进一点窗户外侧就有一部分旧风景移出视野同时另一部分新风景进入视野。中间大部分风景其实一直在那里只是位置移动了一点。2.2 从暴力到滑窗的代码演化第一步先算第一个窗口的和也就是前 k 个元素的和。int windowSum 0; for (int i 0; i k; i) { windowSum nums[i]; }第二步窗口从索引 k 开始向右移动每次移动时做“减旧加新”int maxSum windowSum; for (int i k; i nums.length; i) { windowSum windowSum - nums[i - k] nums[i]; maxSum Math.max(maxSum, windowSum); }第三步平均值就是 maxSum / (double) k。完整代码如下public double findMaxAverage(int[] nums, int k) { int windowSum 0; for (int i 0; i k; i) { windowSum nums[i]; } int maxSum windowSum; for (int i k; i nums.length; i) { windowSum windowSum - nums[i - k] nums[i]; maxSum Math.max(maxSum, windowSum); } return (double) maxSum / k; }这里有个细节我要特别说明一下很多人会先把maxSum初始化为 0这在数组全是正数时没问题但一旦数组里有负数就会出错。比如 nums [-5, -1, -2], k 2所有长度为 2 的子数组最大和是 -3如果你把maxSum初始化成 0最后返回值就是 0显然不对。正确的做法是把maxSum初始化为第一个窗口的和也就是windowSum的初始值然后从第二个窗口开始比较。这样无论数组里有没有负数结果都不会出错。2.3 为什么不需要维护窗口的左边界指针有人可能会问滑动窗口通常不是用两个指针 left 和 right 来维护吗为什么这里只用一个循环变量 i因为这里的窗口长度是固定的永远是 k。left 和 right 之间的关系是确定的right left k - 1。所以不需要像“无重复字符的最长子串”那样同时维护两个指针——固定长度窗口的边界位置可以直接算出来这也是本题作为滑动窗口入门题的原因之一。3. 三种主流写法对比以及边界条件实测3.1 写法对比滑窗、双指针、前缀和除了前面那种标准的滑动窗口写法我在实际刷题中还见过另外两种常见写法这里一并做一个对比。写法核心思想时间复杂度空间复杂度适用场景滑动窗口维护固定长度窗口减旧加新O(n)O(1)本题最佳方案双指针left 和 right 同步右移O(n)O(1)本质上是滑窗的另一种写法前缀和预处理前缀和数组再相减O(n)O(n)窗口长度动态变化时更通用双指针写法长这样public double findMaxAverage(int[] nums, int k) { int left 0; int sum 0; double maxAvg -Double.MAX_VALUE; for (int right 0; right nums.length; right) { sum nums[right]; if (right - left 1 k) { maxAvg Math.max(maxAvg, (double) sum / k); sum - nums[left]; left; } } return maxAvg; }这段代码的逻辑是right 指针逐个加入元素当窗口长度达到 k 时计算平均值并更新结果然后 left 指针右移一位把左边滑出的元素从 sum 中减掉。这种写法的好处是如果面试官把题目改成“子数组最大平均数 II”k 不固定你在双指针基础上稍作修改就能过渡到新的解法。坏处是不如第一种写法直观初看时容易绕。前缀和写法public double findMaxAverage(int[] nums, int k) { int n nums.length; int[] prefix new int[n 1]; for (int i 0; i n; i) { prefix[i 1] prefix[i] nums[i]; } int maxSum Integer.MIN_VALUE; for (int i k; i n; i) { maxSum Math.max(maxSum, prefix[i] - prefix[i - k]); } return (double) maxSum / k; }前缀和写法的思路是提前算好每个位置之前的累积和然后两个前缀和相减就能得到任意区间的和。这样做的好处是区间求和变成了 O(1) 操作坏处是额外使用了一个长度为 n1 的数组空间复杂度是 O(n)。如果你只是做这一道题我推荐第一种写法如果你在准备面试三种都要能写出来因为面试官可能让你对比它们的优劣。3.2 边界条件实测记录我在本地反复跑过各种测试用例这里把我认为值得注意的边界情况列出来第一个k 1。此时每个子数组只有一个元素最大平均值就是数组中的最大值。滑动窗口的循环从 i 1 开始每一步都只比较单个元素的大小逻辑正确。第二个k nums.length。此时整个数组只有一个子数组结果就是整个数组的平均值。第一个窗口的和等于数组总和循环条件i nums.length不成立直接返回第一个窗口的平均值即可。第三个数组元素全是负数。前面已经说过maxSum不能初始化为 0必须初始化为第一个窗口的和。第四个数组长度为 1k 也为 1。这两个条件同时满足时第一个窗口的和就是唯一的元素循环不会进入直接返回该元素本身。第五个数组元素是小数。这里有个细节要看仔细——力扣的这道题里nums 是整数数组但有些变体题目里 nums 可能是浮点数数组。如果是浮点数sum 的类型就要用 double否则小数部分会被截断。4. 刷题现场最容易踩的四个坑4.1 用 int 存窗口和导致溢出这是我在真实面试中见过的问题也是最隐蔽的坑之一。题目中 nums[i] 的范围是 -10^4 到 10^4nums.length 最大是 10^5所以窗口和的最大值是 10^4 * 10^5 10^9这个值还在 int 的范围内int 最大值约 2.1 * 10^9。但注意这只是这道题的范围。如果面试官把 nums[i] 的范围改成 -10^5 到 10^5数组长度改成 10^6窗口和就是 10^11明显超出 int 范围。所以我在写这道题时习惯直接把windowSum声明成 long虽然在这道题里有点大材小用但能避免后续修改范围时忘记改类型导致溢出。maxSum同样用 long只有在最后计算平均值时才转为 double。4.2 求平均值时的精度问题返回平均值时maxSum / k是整数除法结果会被截断。比如 maxSum 7, k 2整数除法结果是 3而不是 3.5。正确的做法是先把分子转成浮点数再除(double) maxSum / k。还有一种写法是maxSum * 1.0 / k效果一样。4.3 死记模板不懂变通滑动窗口的通用模板一般是int left 0; for (int right 0; right n; right) { // 扩大窗口 while (窗口不满足条件) { // 收缩窗口 left; } // 更新答案 }但这个模板是针对“窗口长度不固定”的问题设计的。到了这道固定长度窗口的题很多初学者套模板时不知道该在哪里更新答案甚至把 left 写在条件判断外面导致窗口长度不是 k。我的建议是遇到固定窗口长度的题目优先使用第一种写法先算第一个窗口再逐个滑动这样逻辑最清晰不容易出错。等你对滑动窗口足够熟练之后再尝试双指针写法。4.4 忽略题目对输出格式的要求题目要求输出结果与精确值相差不超过 10^-5 即可也就是说你不用刻意保留几位小数直接返回 double 就行。但我在力扣评论区看到有人用 String.format 把结果格式化成了两位小数再返回结果在精度要求更严的测试用例上挂掉了。5. 从这道题延伸出去的滑窗家族5.1 变体一子数组最大平均数 II二分答案力扣 644 题“子数组最大平均数 II”是这道题的进阶版。区别在于k 不再固定而是一个最小值约束——你要找出长度至少为 k 的子数组的最大平均值。这时候滑动窗口不能直接用了因为你不知道窗口到底该开多大。常见的解法是二分答案猜一个平均值 mid然后检查是否存在长度至少为 k 的子数组的平均值大于等于 mid。检查方法是把每个元素减去 mid再找长度至少为 5 的最大子数组和是否大于等于 0。这里用到了前缀和的最小值维护和“最大子数组和”问题有异曲同工之妙。这道题我没法在这里展开细讲但你可以把它作为刷完 643 之后的下一道练习题。5.2 变体二最大子数组和Kadane 算法力扣 53 题“最大子数组和”和本题看起来像但解法完全不同。本题是固定窗口长度用滑动窗口53 题是求最大连续子数组和不限制长度用 Kadane 算法——核心是“如果之前的累加和为负数就舍弃从当前元素重新开始”。为什么 53 题不能直接套滑动窗口因为窗口长度不确定滑动窗口的“减旧加新”逻辑不成立。这两道题放在一起对比着刷能帮你更清楚地理解“什么时候用滑动窗口什么时候用动态规划”。5.3 变体三定长滑窗的其他经典题掌握固定长度滑动窗口后可以顺手把这几道题一起刷了力扣 239 题“滑动窗口最大值”窗口长度固定为 k但需要额外维护一个双端队列来快速获取窗口内的最大值。力扣 567 题“字符串的排列”窗口长度固定需要统计窗口内字符频次与目标字符串是否匹配。力扣 438 题“找到字符串中所有字母异位词”同样是定长窗口加频次统计。这几道题的核心思想一致都是维护一个长度固定的窗口区别只在于窗口内信息的统计方式不同。把它们放在一起刷能形成体系化的记忆比一道一道孤立地刷效率高得多。6. 刷题和面试中的几条实用心得6.1 做题前先算时间复杂度我刷题有个习惯在写代码之前先看一眼数据范围估算暴力解法的复杂度判断是否会超时。以本题为例nums.length 最大是 10^5双重循环的复杂度约是 10^10必然超时。这时候就要想优化策略。这种“先估复杂度再动笔”的习惯能帮你避免很多无效编码。6.2 面试时主动讲出优化过程如果面试官让你做这道题不要直接给出滑动窗口的最终代码。先给暴力解法说明它的复杂度问题再一步步推导出滑动窗口。这一步是面试官考察的重点——他们想看到你的思考过程而不仅仅是结果。我之前模拟面试的时候遇到过类似场景候选人一上来就写出最优解面试官反而追问了一句“你能解释一下为什么这个解法是正确的吗”如果没有提前想清楚正确性证明这一问很容易卡壳。6.3 正确性证明的简单思路这道题的正确性证明其实很直白第一个窗口的和是 nums[0] 到 nums[k-1] 的和第二个窗口通过减去 nums[0] 加上 nums[k] 得到数学上可以展开第二个窗口的和 (nums[0] ... nums[k-1]) - nums[0] nums[k] nums[1] ... nums[k]。以此类推每次滑动都准确对应下一个长度为 k 的连续子数组。因此遍历所有窗口后得到的最大值就是全局最大值。这段推导可以在 1 分钟内讲完面试时很加分。6.4 刷题记录与复盘建议我建议刷完这道题后在你的刷题笔记里记录三件事第一用一句话概括题目本质固定长度窗口内求最大平均值。第二写清最优解法的复杂度时间 O(n)空间 O(1)。第三标记一个易错点maxSum 初始化不能用 0。这样再过两周回来复习时不需要重新读题就能快速回忆起来。我个人经验是滑窗类问题连续刷 5 到 8 道之后会有一种“顿悟感”之后遇到新的变体基本都能自己推出来。最后分享一个调试小技巧本地测试时除了力扣给的示例一定要自己构造几组极端数据。比如全负数数组、k 等于数组长度、数组只有一个元素、k 等于 1。这几组数据能覆盖大部分边界条件帮你提前发现代码里潜在的问题而不是等提交之后被测试用例“教做人”。