如果你刷 LeetCode 刷到一定阶段一定会碰上一类题给你一个数组让你找满足某个条件的最短或者最长连续区间。209. 长度最小的子数组Minimum Size Subarray Sum就是这类题里最经典的一道坎。题目本身不难读懂给定一个正整数数组 nums 和一个正整数 target找出数组中满足“元素之和大于等于 target”的连续子数组返回最短长度如果不存在返回 0。但这道题有意思的地方在于它几乎是所有“滑动窗口”入门教程都会选用的第一道例题。面试里问这道题往往不是考你会不会暴力解而是想确认你懂不懂双指针为什么能优化到 O(n)。这篇文章我会从暴力解法出发把滑动窗口和前缀和加二分两种主流写法全部拆开讲包括代码、时间复杂度和每一处边界条件的取舍最后把我自己刷题时踩过的坑和排查思路也一并写出来。适合刚开始刷数组类题目的同学也适合准备面试想系统捋一遍滑动窗口套路的同学。1. 题目到底在问什么先读懂“长度最小”的限制1.1 暴力解为什么不可行拿到这道题最容易想到的思路就是枚举所有连续子数组对每个子数组求和找到第一个满足条件的长度。写起来很直觉def minSubArrayLen(target, nums): n len(nums) ans float(inf) for i in range(n): total 0 for j in range(i, n): total nums[j] if total target: ans min(ans, j - i 1) break return 0 if ans float(inf) else ans这个解法的时间复杂度是 O(n²)。当数组长度 n 到 10^5 级别时最坏情况下要计算大约 5×10^9 次加法在力扣这样的在线评测环境里基本不可能跑完。即便你优化成“固定左端点右端点只往后扫直到和超过 target 就 break”遇到整个数组的和刚好略小于 target 的极端用例内层循环仍然要走到最后复杂度退化回去。所以这道题的核心难点恰恰不是“怎么求子数组和”而是“怎么在移动过程中复用已经算过的和”避免重复计算。而所有能复用的地方都来源于题目里隐藏的一个关键特性数组元素全是正整数。1.2 从“连续子数组”想到滑动窗口题目要求的是连续子数组而不是子序列。“连续”意味着我们可以把数组看成一条从左到右延伸的长条然后在上面框出一个窗口窗口左右边界就是子数组的起点和终点。因为所有元素都是正整数所以窗口内元素之和有一个单调的性质固定左边界右边界向右移动和只会越来越大固定右边界左边界向右移动和只会越来越小。这个单调性非常关键它让我们在移动边界时可以明确判断“该扩还是该缩”而不用回头重新扫描这就是滑动窗口能成立的数学基础。打个比方想象你在一排货架上找一段连续的货物让总价达到某个门槛。你右手从左边开始一件一件往右拿钱够了就停下来然后左手从右边开始往回退货物直到价格刚好低于门槛。接着右手又继续往右拿循环这个过程。你每次只移动一只手不需要把手里的货全部放下重新数一遍这就是滑动窗口的直观过程。2. 滑动窗口解法双指针如何做到 O(n)2.1 窗口的扩张与收缩逻辑滑动窗口的写法通常用两个指针 left 和 right初始都指向数组开头。right 作为窗口右边界一步一步向右遍历数组每次把 nums[right] 加进当前和 sum一旦 sum target说明当前窗口已经满足条件此时尝试移动 left 来收缩窗口看能不能找到更短的满足条件的子数组。这里的核心逻辑是在一个窗口满足条件的前提下左指针每右移一位总和就会变小可能仍然满足条件也可能立刻不满足。所以我们需要用 while 循环而不是 if 判断持续收缩直到 sum target。每收缩一次就记录一次当前窗口长度和已有的最小长度取较小值。等收缩完right 继续前进重复这个过程。为什么这个方法不会漏掉正确答案因为 right 在遍历过程中以每个 right 作为子数组右端点时left 都已经被推到了“能够让 sum target 的最靠右的位置”也就是对于当前右端点来说窗口已经被压缩到了最短。所有可能成为答案的连续子数组它的右端点一定会在某个时刻被 right 扫到而那一刻 left 会停留在恰好满足条件的最短位置上。两个指针都只往一个方向移动没有回退所以整体是 O(n)。2.2 代码实现C 与 Python 双版本先看 C 版本这也是我在笔试里最常用的写法class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int left 0; long long sum 0; int ans INT_MAX; for (int right 0; right n; right) { sum nums[right]; while (sum target) { ans min(ans, right - left 1); sum - nums[left]; left; } } return ans INT_MAX ? 0 : ans; } };Python 版本逻辑完全一致只是语法更简洁class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: left 0 total 0 ans float(inf) for right in range(len(nums)): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ans注意一个细节在 while 循环内部我先把当前窗口长度拿来更新 ans再移动 left。这和“先移动 left 再更新 ans”在数学结果上是等价的因为每次进入 while 循环时窗口必然满足条件你记录的是收缩前的状态还是收缩后的状态最终都会被 min 函数过滤成最小值。但先记录再收缩的逻辑更直观不容易写混。2.3 每个关键细节的为什么等号、循环、边界第一次写这道题的人最容易在三个地方犯迷糊。第一为什么是sum target而不是sum target题目要求的是“大于等于 target”等于是最低要求大于同样满足。如果你只判断相等窗口收缩时一旦总和刚好超过 target 但又等于不了就会漏掉答案。所以必须用大于等于。第二为什么收缩要用while我们手动模拟一组数据就明白了。假设 target 7nums [2, 3, 1, 2, 4, 3]。当 right 走到下标 3 时窗口是 [2, 3, 1, 2]sum 8满足条件。如果这里用 ifleft 只会从 0 移到 1窗口变成 [3, 1, 2]sum 6不符合条件那么你记录的最短长度就是 4。可实际上后面 right 走到下标 4 时窗口 [3, 1, 2, 4] 的 sum 10left 收缩两步到下标 2 时 [1, 2, 4] 还是满足的不对[1, 2, 4] 的 sum 7正好满足长度是 3。所以最终的 3 在后续迭代里仍会被找到。但如果你在每一步都用 if 判断而非 while在某些数据组合下确实可能错过更短的窗口。比如 target 很大、窗口很长的情况一次收缩后仍然满足if 只收缩一步就停止了而 right 移动前这个窗口就已经有更短的可能。因此收缩必须用 while 收缩到不满足为止才能保证对每个右端点都找到最短的窗口。第三为什么sum在 C 里要声明为long long根据题目约束target 最大可以到 10^9nums[i] 最大可以到 10^4n 最大可以到 10^5。理论上整个数组的和最大能到 10^9这个值已经逼近 32 位 int 的上限 2,147,483,647。虽然大多数测试数据不会卡在极限但用long long可以完全杜绝溢出的风险。面试时主动写出long long也是一个得分点说明你考虑到了数据范围。3. 第二种解法前缀和 二分查找3.1 前缀和数组如何构造滑动窗口确实是这道题的最优解但面试里常有人追问“如果数组里有负数滑动窗口还成立吗”这个问题先放一边我们先掌握另一种解法前缀和加二分查找。它的思路是把“子数组求和”转换成“前缀和数组上的区间差值”。构造一个长度为 n1 的前缀和数组 sums其中 sums[0] 0sums[i] 表示原数组前 i 个元素的和。也就是sums[0] 0 sums[1] nums[0] sums[2] nums[0] nums[1] ... sums[i] nums[0] ... nums[i-1]这样一来从下标 i 到下标 j-1 的子数组和就等于sums[j] - sums[i]。这个转化在很多数组题里都是标配大家一定要熟练。因为题目保证 nums 全是正整数所以 sums 数组是严格单调递增的。这个单调性给了我们一个重要的便利给定一个目标值我们可以用二分查找在 sums 里快速找到第一个前缀和大于等于某个阈值的下标。3.2 lower_bound 精准定位最短长度我们的目标可以重新表述为对每个可能的子数组起点 i找到一个最小的终点下标 j使得sums[j] - sums[i] target。移项后就是sums[j] sums[i] target。由于 sums 单调递增我们可以在sums的索引范围[i1, n]内二分查找第一个大于等于sums[i] target的位置。找到后子数组长度就是j - i。这里下标 j 对应的是前缀和数组的下标不是原数组的下标所以长度计算不要写错。C 实现可以直接调用lower_boundclass Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long sums(n 1, 0); for (int i 0; i n; i) { sums[i 1] sums[i] nums[i]; } int ans INT_MAX; for (int i 0; i n; i) { long long need sums[i] target; auto it lower_bound(sums.begin() i 1, sums.end(), need); if (it ! sums.end()) { int j it - sums.begin(); ans min(ans, j - i); } } return ans INT_MAX ? 0 : ans; } };注意lower_bound的搜索起点是sums.begin() i 1而不是sums.begin()。这样做有两个原因一是子数组至少包含一个元素所以终点必然大于起点二是如果把起点之前的前缀和也放进搜索范围可能找到j i的情况得到长度为 0 的错误答案。如果你不想依赖库函数也可以手写二分。模板如下int lo i 1, hi n; while (lo hi) { int mid (lo hi) / 2; if (sums[mid] need) { hi mid; } else { lo mid 1; } } if (lo n) { ans min(ans, lo - i); }这个手写版本用的是“找左边界”的二分模板判断条件是sums[mid] need满足时往左收缩不满足时往右收缩。写熟这个模板以后遇到二分找边界的题都能直接套。3.3 两种解法如何选择滑动窗口的时间复杂度是 O(n)空间复杂度 O(1)前缀和加二分的时间复杂度是 O(n log n)空间复杂度 O(n)。单从性能上看滑动窗口全面占优。那为什么还要学第二种解法因为滑动窗口有一个隐含前提窗口内元素之和必须具有单调性也就是数组元素全为正数。一旦题目改成允许负数比如力扣 862 题“和至少为 K 的最短子数组”left 和 right 的移动逻辑就不成立了right 右移时 sum 可能变小窗口满足条件后 right 收缩也可能再次满足条件乱成一团。这时候前缀和思路反而有用武之地配合单调队列可以把复杂度控制在 O(n)。所以我的建议是这道题本身用滑动窗口但前缀和加二分的写法也要能默写出来。面试官如果问“还有没有别的解法”你只要能流畅说出第二种说明你对这个知识点的理解是有深度的。而且前缀和的构造在很多其他题目里是前置步骤写顺了不亏。4. 笔试面试高频坑位5 个必踩的雷4.1 用 if 还是 while 收缩窗口这个问题我在前面提到过但值得单独再说一遍。很多人在第一次写这道题时都会写成while total target: # 错误示例 right 1 total nums[right] if total target: ans min(ans, right - left 1) left 1这种写法相当于把“扩展”写在 while 里把“收缩”写在 if 里逻辑上完全跑偏了。正确的模型是扩展在 for 循环里自动发生收缩才用 while 处理。扩展是必然动作收缩是条件动作。把主次搞反了代码会变得很难调试而且容易数组越界。我的排查技巧是在写代码之前先在注释里写清三个问题。窗口什么时候扩张窗口什么时候收缩窗口满足什么条件时更新答案想清楚再动键盘比写完后反复调试效率高得多。4.2 结果初始值为什么必须用最大值ans的初始值必须是最大值比如INT_MAX或float(inf)不能是 0。因为我们要用min来更新答案如果初始值是 0那么任何窗口长度都会被 0 覆盖最后永远返回 0。还有一种写法是这样的初始化ans n 1。因为子数组最长不会超过 n所以n 1是一个比所有合法长度都大的值用它做初始值也完全没问题。最后判断时如果ans还是n 1说明没有找到满足条件的子数组返回 0。这个技巧在某些语言里比INT_MAX更直观不会牵扯到类型上限问题。4.3 溢出问题与类型选择前面提过用long long规避溢出这里再补充一个容易被忽略的细节前缀和数组里存放的也是累加和同样需要用long long。有些同学只在滑动窗口的 sum 变量上用了 long long写第二种解法时前缀和 vector 用vectorint结果在累加过程中就溢出了二分查找的结果自然不对。还有一个关于二分的坑need sums[i] target这个值也可能非常大接近 2×10^9 级别如果不声明为long long在 C 里同样存在溢出风险。写代码时宁可全部用 long long也不要精确计算“这个值一定不超过 int”毕竟评测数据往往比你想象的更极限。4.4 边界测试用例表调试这道题时我建议至少准备下面几组测试数据测试场景输入预期输出说明正常用例target 7, nums [2,3,1,2,4,3]3标准示例验证滑动窗口基本逻辑单元素满足target 3, nums [3]1验证长度为 1 的窗口全部元素和刚好够target 10, nums [1,2,3,4]4验证 right 走到末尾仍然满足不存在答案target 100, nums [1,2,3]0验证返回值兜底逻辑单个元素就达标target 1, nums [1,1,1]1验证窗口收缩到 left 超过 right大数边界target 1000000000, nums 长度 10^5许多验证 long long 是否使用第 5 条值得展开说一下当 nums[0] 本身就大于等于 target 时第一次进入 while 就会把 left 加到大于 right窗口变成空。但下一次 for 循环 right 继续右移时left 已经指向 right 的位置窗口会重新从新元素开始累积不会出现元素被重复计算的情况这正是滑动窗口的自我修复能力。5. 从这道题看滑动窗口的通用套路5.1 可套用的模板刷完这道题最有价值的产出其实是一个可以复用的滑动窗口模板。以我的经验最稳定的模板是下面这个框架int left 0; int ans 0; // 或者 INT_MAX视题目要求最值而定 WindowState window; // 用变量或数据结构维护窗口状态 for (int right 0; right n; right) { // step 1: 把 nums[right] 加入窗口状态 // step 2: 当窗口不满足题目约束时收缩 left while (window 不满足约束) { // 如果题目求最短在这里更新 ans // 把 nums[left] 移出窗口状态 left; } // 如果题目求最长在这里更新 ans }关键区别在于求最短满足条件的问题通常在“收缩”过程中更新答案因为收缩到极限时窗口刚好满足条件求最长满足条件的问题通常在收缩结束、窗口恢复合法后更新答案因为这时窗口是当前 right 下最长的合法窗口。209 这道题属于前者所以我把ans min(ans, right - left 1)写在 while 循环内部。把这两个更新位置分清滑动窗口类题目基本就解决了一半。5.2 扩展到变形题滑动窗口的变形题本质上都只是把“窗口状态”换了一种维护方式。我刷过以后觉得最有代表性的有三个力扣 76 题“最小覆盖子串”窗口状态从数字和变成字符频次收缩条件变成“当前窗口已经覆盖了 t 的所有字符”答案更新也是在收缩过程中。力扣 3 题“无重复字符的最长子串”窗口状态是字符集合收缩条件是“出现重复字符”且求的是最长所以 ans 更新放在收缩结束后。力扣 904 题“水果成篮”窗口状态是水果种类计数收缩条件是“种类数超过 2”同样求最长更新位置在收缩后。做这些变式题的时候你会发现核心套路没变right 负责扩张left 负责收缩答案更新位置由“求最短还是求最长”决定。唯一要额外动脑的是“窗口状态怎么维护”但这属于数据结构选型问题已经和双指针本身的逻辑脱钩了。就我个人刷题的习惯来说做滑动窗口题最管用的一个动作是在草稿纸上把 right 一步步移动、窗口一步步收缩的过程完整画出来。像前面nums [2, 3, 1, 2, 4, 3]这个例子画完一遍while 和 if、ans 更新位置这些坑基本都能躲开。你甚至可以每道题都先手动模拟一遍再写代码速度反而比直接上手更快。209 这道题能延伸出来的类似题很多但只要你把“什么时候扩、什么时候缩、什么时候更新答案”这三件事想清楚往后遇到同类型题就不会慌。