力扣209这道题是我在面试里见到的最高频的“滑动窗口”入门题之一也是很多刷题人正式接触双指针的起点。题目看起来平淡无奇——在一个只含正整数的数组里找一个最短的连续子数组让它的和至少达到给定的 target找不到就返回 0。但就是这么一道 easy 到 medium 之间的题我在真实面试里见过不少候选人翻车有人一上来写 O(n^2) 暴力有人知道要用滑动窗口却把左右指针的移动顺序写反还有人答不出“为什么这个解法是 O(n)”。这篇文章我打算把这道题彻底讲透。不管你是刚开始刷 LeetCode 的新手还是准备面试想查漏补缺的老手都能从里面拿到一些平时题解里不太会细说的东西。我会从暴力解法讲起再拆滑动窗口的每一步细节最后补充前缀和加二分的另一种思路以及我实际踩过的几个坑。1. 题目理解与场景还原1.1 题面到底在问什么题目对应力扣第 209 题英文名是 Minimum Size Subarray Sum。核心要求可以用三句话概括给定一个只包含正整数的数组 nums和一个正整数 target找出数组中满足“子数组元素之和大于等于 target”的最短连续子数组返回这个子数组的长度如果不存在则返回 0。注意题目里有个容易被忽略的关键限定数组元素都是正整数。这个条件不是随便写的后面滑动窗口解法能成立完全依赖它。如果数组里混进负数整个解法体系就塌了这点我后面会专门解释。举个具体例子就好懂了。target 7nums [2, 3, 1, 2, 4, 3]。肉眼扫一遍可能的子数组[2, 3, 1, 2] 的和是 8长度 4[3, 1, 2, 4] 的和是 10长度 4[2, 4, 3] 的和是 9长度 3而 [4, 3] 的和恰好是 7长度只有 2。所以答案是 2。还有两个边界例子值得留意。一个是 target 4nums [1, 4, 4]答案就是 1因为单个元素 4 已经满足条件这告诉我们最短长度有可能是一个元素。另一个是 target 11nums 全是 1 的数组即使全加起来都不够 11那就直接返回 0。这属于“不存在候选答案”的情况代码里必须处理。1.2 为什么这道题这么值得刷很多人觉得这题简单没什么好说的。但我在带新人时发现它其实处在“会做”和“做对”的分界线上。你也许五分钟就写出了能过的代码但面试官只要追问几个为什么很容易露馅。首先它是滑动窗口类题目的模板题。理解了 209 的窗口伸缩逻辑后面做“无重复字符的最长子串”“最小覆盖子串”“水果成篮”这些题核心套路都是一样的右指针扩展左指针收缩在某个满足条件的时刻更新答案。可以说209 是这一整个题型的地基。其次它能自然考察复杂度分析能力。暴力是 O(n^2)优化后是 O(n)中间跨度很大面试官很喜欢借这种题看候选人有没有优化意识以及能不能讲清楚优化背后的原因。很多人能写出滑动窗口但被问“为什么均摊复杂度是 O(n)”时就卡住了这就是基础不牢的表现。最后这道题在真实面试中出现频率实在太高了。我见过字节、美团、百度这些公司的题目记录里都有它的身影而且往往是作为一面手撕题出现的。与其背一堆高大上的算法模板不如先把这种高频基础题磨到极致。1.3 暴力解法先跑一遍在讲滑动窗口之前先看看朴素解法长什么样。最直接的想法是枚举所有可能的连续子数组外层循环枚举起点 i内层循环枚举终点 j累加 [i, j] 之间的和一旦发现和大于等于 target就更新答案并提前结束内层循环。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int ans INT_MAX; for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum nums[j]; if (sum target) { ans min(ans, j - i 1); break; } } } return ans INT_MAX ? 0 : ans; } };这个解法的时间复杂度是 O(n^2)。有人可能会说内层循环加上 break平均情况下应该没那么差。但最坏情况依然存在比如 target 特别大所有子数组从头加到尾都凑不够 target那每个起点都要把整个数组扫一遍依然逃不出 n^2 的规模。还有一个常见的“伪优化”是用前缀和把内层求和降到 O(1)但仔细算一下枚举子数组起点的 O(n) 没变枚举终点的 O(n) 也没变整体还是 O(n^2)。数据规模到了 10^5 级别n^2 就是 10^10 次操作在 LeetCode 上肯定超时。所以暴力只能用来验证思路不是最终方案。2. 滑动窗口解法核心思路与完整实现2.1 一句话讲清滑动窗口滑动窗口的思想其实一句话就能说完用两个指针 left 和 right 圈住一个“连续子数组”right 负责向右扩展窗口把新元素加进来当窗口内元素和满足sum target时就尝试移动 left 收缩窗口看能不能在保持和仍然不小于 target 的前提下把窗口长度压得更短。可以把它想象成一个可以伸缩的探针右端不停往前探测一旦探测到“够长了”左端就试探着往回缩缩到刚好不能维持条件为止。在这个过程中每一个“够长”的窗口长度都会被记录下来最终取最小值。这个思路的关键在于窗口只向右移动left 和 right 都不会回退。所以每一个元素最多被加进来一次、被减出去一次整个过程是线性的。至于为什么可以放心地只向右移动而不是像暴力那样枚举所有起点这就要回到正整数数组这个前提了。2.2 完整可运行的代码先给 C 版本这是面试中最常写的语言。我习惯用long long来存 sum因为数组元素累加后很可能超过 int 范围提前用 long long 可以省掉一个边界隐患。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, x in enumerate(nums): total x while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ansJavaScript 版本也贴一下方便前端同学var minSubArrayLen function(target, nums) { let left 0; let sum 0; let ans Infinity; for (let right 0; right nums.length; right) { sum nums[right]; while (sum target) { ans Math.min(ans, right - left 1); sum - nums[left]; left; } } return ans Infinity ? 0 : ans; };三份代码的核心结构一模一样只要理解了 C 版其他语言就是换壳。代码里最需要注意的就是while (sum target)这里必须用while而不是if原因我放到第四章细讲。2.3 手把手模拟一次滑窗过程光看代码可能还觉得抽象我拿示例 [2, 3, 1, 2, 4, 3]target 7把整个滑动过程手动走一遍。这一步对新手来说价值很高建议自己也照着画一遍。初始状态left 0sum 0ans 无穷大right 从 0 开始。right 0sum 变成 2小于 7不收缩窗口为 [2]。right 1sum 变成 5小于 7窗口为 [2, 3]。right 2sum 变成 6小于 7窗口为 [2, 3, 1]。right 3sum 变成 8大于等于 7。此时更新 ans 4窗口 [2, 3, 1, 2] 的长度。然后收缩sum 减去 nums[0] 2sum 变成 6left 变成 1。此时 sum 7while 退出窗口变成 [3, 1, 2]。right 4sum 加上 nums[4] 4sum 变成 10满足条件。更新 ans min(4, 4) 4窗口 [3, 1, 2, 4] 长度也是 4。收缩sum 减去 nums[1] 3sum 变成 7left 变成 2此时 sum 仍大于等于 7继续收缩更新 ans min(4, 3) 3窗口 [1, 2, 4] 长度 3。sum 减去 nums[2] 1sum 变成 6left 变成 3while 退出窗口变成 [2, 4]。right 5sum 加上 nums[5] 3sum 变成 9满足条件。更新 ans min(3, 3) 3窗口 [2, 4, 3]。收缩sum 减去 nums[3] 2sum 变成 7left 变成 4sum 仍大于等于 7继续收缩更新 ans min(3, 2) 2窗口 [4, 3] 长度 2。sum 减去 nums[4] 4sum 变成 3left 变成 5while 退出。最终 ans 2与正确答案一致。整个过程中right 一共走了 6 步left 一共走了 5 步两个指针都只前进不后退总计操作次数在 2n 量级这就是线性复杂度的直观来源。2.4 O(n) 复杂度的本质为什么滑动窗口是 O(n)很多人回答说“因为每个元素被访问两次”这个说法其实不够严谨。准确的说法是对于任意一个元素 nums[i]它作为 right 指针指向的元素被“加入”窗口恰好一次它作为 left 指针指向的元素被“移出”窗口最多一次。right 从 0 走到 n-1 一共 n 次left 从 0 最多走到 n-1 一共也是 n 次两个指针都没有回头路。所以总操作次数最多是 2n 次时间复杂度是 O(n)空间复杂度是 O(1)只用了几个变量。这里要注意虽然 while 内部可能执行很多次但所有 left 指针移动的总次数不会超过 n看代码时不要被嵌套的 while 骗了它不是每次外层循环都跑满 n 次。面试的时候我建议这样回答复杂度问题“right 指针只会向前移动 n 次left 指针在整个算法过程中也只会向前移动 n 次因为每个元素最多被移出窗口一次。嵌套的 while 总执行次数是均摊 O(n) 的。”把“均摊”两个字说出来面试官一般就会点头。2.5 为什么必须是正整数数组滑动窗口这个解法有一个隐性前提窗口和随着窗口扩大而单调不减随着窗口缩小而单调不增。只有数组全都是正数或非负数时这个单调性才成立。正因为有这个单调性我们才敢在sum target时放心地收缩 left。收缩后如果 sum 仍然大于等于 target说明我们找到了一个更短的可行子数组应该继续收缩如果 sum 小于 target 了说明当前窗口已经不可行只能让 right 继续往前走。如果数组里出现了负数这个逻辑立刻崩掉。比如窗口 [5, -3, 4]target 是 6。窗口整体和是 6长度 3。你收缩掉 5窗口变成 [-3, 4]和是 1while 退出了。但有没有可能“先收缩掉 -3 或从另一个方向缩”能发现更短的窗口有但滑动窗口的左指针只能从左往右缩它永远没有办法处理这种“窗口内存在负数导致局部和可以任意波动”的情况。所以遇到含负数的类似题目需要换用前缀和加有序结构等思路后面我会拐个弯提一下。3. 前缀和 二分查找另一种解法3.1 前缀和数组的单调性滑动窗口已经是 O(n) 最优解了为什么还要讲前缀和加二分两个原因一是它在面试中是很漂亮的备选方案能展示你知识广度二是它引出的“前缀和数组 二分查找”组合在很多数组题里都能复用。定义前缀和数组 prefix其中 prefix[i] 表示 nums 前 i 个元素的和prefix[0] 0。举例来说nums [2, 3, 1, 2, 4, 3] 对应的 prefix 就是 [0, 2, 5, 6, 8, 12, 15]。这里有个关键的数学性质对于任意子数组 nums[i..j]左闭右闭它的和可以写作prefix[j1] - prefix[i]。因为 nums 全是正整数所以 prefix 数组是严格递增的。严格递增意味着 prefix 里可以放心使用二分查找——我们要找的“某个下标”可以用标准的 lower_bound 在 O(log n) 时间内定位。3.2 二分查找推导与代码思路是这样的固定子数组的起点 i我们要找一个最小的终点 jj i使得prefix[j1] - prefix[i] target。移项一下就变成prefix[j1] prefix[i] target。因为 prefix 严格递增这个问题就是在 prefix 数组的指定区间里找第一个大于等于prefix[i] target的位置。找到之后j - i 1就是子数组长度其中 j 是终点下标转换成 prefix 下标就是 k - i其中 k 是二分找到的 prefix 下标。C 代码class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] nums[i - 1]; } int ans INT_MAX; for (int i 0; i n; i) { long long need prefix[i] target; // 在 prefix 数组 [i1, n] 范围内找第一个 need 的位置 auto it lower_bound(prefix.begin() i 1, prefix.end(), need); if (it ! prefix.end()) { int len it - prefix.begin() - i; ans min(ans, len); } } return ans INT_MAX ? 0 : ans; } };Python 版本用 bisect_leftimport bisect class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] nums[i - 1] ans float(inf) for i in range(n): need prefix[i] target idx bisect.bisect_left(prefix, need, i 1, n 1) if idx n: ans min(ans, idx - i) return 0 if ans float(inf) else ans这段代码有两个细节值得说。第一个是lower_bound的查找范围从prefix.begin() i 1开始保证子数组至少包含一个元素避免出现“空窗口”。第二个是 prefix 用long long因为 n 最大可以到 10^5每个 nums[i] 最大到 10^9累加和完全可能超过 int 上限用 long long 才安全。3.3 两种解法的对比与选择解法时间复杂度空间复杂度核心优势适用前提暴力枚举O(n^2)O(1)简单直观好写数据量小滑动窗口O(n)O(1)最优时间代码短数组非负前缀和 二分O(n log n)O(n)思路通用可扩展prefix 单调从纯算法效率上说滑动窗口明显更优空间也更省。但在面试场景里先说出滑动窗口再补一句“这道题其实也可以用前缀和加二分做时间复杂度 O(n log n)因为前缀和严格递增”会显得你对解法体系有完整认知。还有一点值得思考如果题目改成“数组里有负数但要找最短连续子数组和至少为 target”滑动窗口就失效了但前缀和数组也不再单调二分同样用不了。这种情况下常见手段是转成求“前缀和差大于等于 target 的最短距离”问题可以用线段树或平衡树来维护前缀和信息。这个扩展比较深面试很少考但了解思路能帮你建立更完整的知识网络。4. 实战场上最容易翻车的细节4.1 初始化值答案变量怎么设这道题一个常见的错法是把 ans 初始化为 0然后最后直接返回 ans。这么做的问题是当真的存在可行答案时min(0, 1)永远是 0答案会被错误地截成 0。所以 ans 必须初始化成一个“不可能成为答案”的大数。C 里习惯用INT_MAXPython 里用float(inf)JavaScript 里用Infinity。最后统一判断一次如果 ans 还是那个初始值说明整个扫描过程中从没找到过满足 sum target 的窗口这时候才返回 0。这里我建议把“初始化 最终判断”作为一个固定组合来记。很多滑动窗口题都有这个套路不只是本题。4.2 while 还是 if收缩必须收缩到底这是新人最容易踩的坑。有人觉得窗口和一旦超过 target只要把 left 往右挪一次就够了用 if 就行。但真实情况是收缩一次之后窗口很可能仍然满足条件此时还能继续收缩从而找到更短的答案。还是刚才那个例子nums [1, 1, 1, 1]target 2。当 right 走到下标 3 时sum 4满足条件。如果用 if收缩一次后窗口变为 [1, 1, 1]sum 3仍然满足条件但 if 已经执行完了不会继续收缩于是错失了长度为 2 的最优答案。所以这里必须用 while在不断收缩的过程中每收缩一步都检查一次 sum 是否仍然大于等于 target。只有收缩到 sum target 时才停下让 right 继续扩展。这个 while 本质上是“把当前窗口压到刚好不再可行的状态”。4.3 答案更新的正确位置答案更新为什么要放在 while 循环体内部这一点很多人没想明白。原因很简单只有在sum target的时刻当前窗口才是一个“合法候选答案”此时它的长度才有资格参与比较。一旦退出 while 循环sum 一定是小于 target 的此刻窗口不再合法如果拿它的长度去更新 ans就会统计到一个错误的、并不满足条件的窗口。所以标准写法是在 while 循环体内的第一行更新 ans然后再执行sum - nums[left]; left。这个顺序不能反。我见过有人把 ans 更新写在循环外部结果跑出来的答案总是偏大就是因为统计了不合法窗口。为了保证正确性可以这样记窗口的状态要么是“合法”要么是“非法”我们只在合法状态下记录长度然后立刻尝试破坏这个合法状态通过收缩接下来要么找到更短的合法状态要么退出循环等待右指针扩展。4.4 边界情况一览几个容易被测试用例打到的边界整理成速查表场景预期结果代码里怎么处理nums 为空数组返回 0for 循环不执行ans 保持初始值最后判断返回 0target 大于数组总和返回 0while 永远不进ans 保持初始值最后判断返回 0target 恰好等于某个单元素返回 1right 扩展时 sum target更新 ans 1left 移动到超过 right窗口为空属正常while 退出后 left 可能等于 right 1后续 right 继续扩展即可sum 累加超过 int 范围必须用 long longC 里 sum 和 prefix 都声明为 long long关于“left 超过 right”这一点我多解释一句。比如 nums [100]target 7right 0 时 sum 100进入 while 后更新 ans 1然后 sum 减掉 100 变成 0left 变成 1。此时 left right窗口为空。如果没有下一个元素算法结束如果有下一个元素下一轮 right 变成 1窗口自动从下标 1 开始。整个过程完全正常不要因为 left 跑到了 right 后面而慌张也不要手动把 left 拉回 right那样反而会引入 bug。还有一个小细节是 while 循环里sum - nums[left]时要保证 left 没有越界。但由于这个操作只发生在 sum target 的前提下而 target 是正整数所以 sum 至少能减掉一个元素left 最多增加到 right 1不会越界访问。这个不变量其实很巧妙建议自己画一画体会一下。5. 从209出发延伸题目与面试追问5.1 一张表看懂滑动窗口变体刷完 209 以后滑动窗口还有一系列变体题很适合放在一起对比着练。我整理了四个最具代表性的题目窗口语义收缩条件答案更新时机核心差异3. 无重复字符的最长子串不含重复字符的连续子串窗口内有重复字符窗口内无重复时更新用 set 判断重复不是数值求和76. 最小覆盖子串覆盖 T 中所有字符的最短子串窗口已覆盖全部字符覆盖完整时收缩并更新用哈希统计字符缺口1004. 最大连续1的个数 III最多翻转 K 个 0 的连续 1 子数组窗口内 0 的个数超过 K0 的个数合法时更新窗口统计的是 0 的数量904. 水果成篮水果种类不超过 2 种的最长连续子序列窗口内种类数超过 2种类合法时更新用哈希表维护种类计数你仔细看会发现这些题的骨架几乎一模一样右指针扩展、当某个“限制条件”被打破时收缩左指针、在条件重新合法时更新答案。209 里条件是和的大小其他题里条件换成了字符覆盖、重复检测、种类数量。把 209 的模板吃透再去做这些题思路会顺很多。5.2 面试官常问的四个追问为什么不先对数组排序答题目要求“连续子数组”排序会破坏元素在原数组中的相对位置连续性和顺序就没了所以不能排序。如果数组里有负数怎么办答滑动窗口的前提是窗口和单调变化有负数时不满足。此时需要换思路比如转为前缀和问题用有序结构维护候选下标但整体复杂度会变高。如果题目要求返回最短子数组本身而不是长度怎么办答在更新 ans 时额外用两个变量记录当前的 left 和 right最后从 nums 里截取这段即可。如果要求“和大于 target”而不是“大于等于”怎么办答把窗口收缩条件从sum target改成sum target其余逻辑完全不变。这四个追问在面试里出现的概率很高。特别是第一个和第二个很多候选人明明写出了正确代码却答不上来给面试官的印象就会打折扣。建议提前把答案组织好形成肌肉记忆。5.3 我常用的“三步做题法”刷这类滑动窗口题我把自己的思考过程总结成三步分享给你。第一步确定窗口的语义。这道题的窗口是什么是满足“和大于等于 target”的一个连续子数组。先想清楚窗口代表什么后续逻辑才有意义。第二步确定扩展和收缩规则。right 指针向右扩展时窗口状态如何变化left 指针向右收缩时什么条件下可以收缩、什么条件下必须停止结合题目限制条件定义清楚。第三步确定答案更新时机。在窗口满足条件时更新还是在窗口不满足条件时更新本题是在满足条件时更新其他题则各不相同。这一步最容易出错一定要结合窗口语义去推。用这三步去套 209、套第 5.1 节里的所有变体题你会发现每道题都只是把第二步和第三步的条件换一换而已。这个方法比死记硬背模板要可靠得多。6. 一些面试实战中的个人经验6.1 白板面试怎么讲好这道题我见过的理想答题节奏是这样的先花三十秒读题用一两个例子跟面试官确认自己理解正确。然后不要直接写滑动窗口而是先说“最朴素的做法是枚举所有子数组O(n^2)数据一大会超时”再看一眼题目条件发现全是正整数于是引出滑动窗口。讲滑动窗口的时候手上可以配合着画图把 left 和 right 画成两个箭头手动演示两三个窗口的伸缩过程。这个动作非常加分它表明你不仅记住了代码还理解了指针移动的含义。等面试官点头了再动笔写代码。写完代码别急着说“好了”自己拿一个用例在脑子里过一遍确认没有越界、没有漏更新再交给面试官。这一整套流程走下来就算有小瑕疵印象分也不会差。6.2 一套值得长期练习的复盘方法我自己的习惯是刷完一道题之后不会立刻跳到下一道而是会问自己三个问题为什么这个解法成立复杂度为什么是这样题目哪个条件变了会让解法失效在 209 这道题上答案分别是正整数保证了窗口和的单调性所以滑动窗口不遗漏最优解每个元素作为右指针进入一次、作为左指针离开一次总操作 O(n)一旦出现负数单调性消失滑动窗口就不能直接成立。这三句话能答上来这道题才算真正吃透。如果你正在准备面试我建议把 209 和它那串变体题放在同一天集中刷完用我说过的三步法去套然后再隔两三天回来默写一遍核心代码。这种强度的刻意练习比零散地刷五十道简单题有用得多。我自己带过的人里凡是能独立讲清楚这道题原理的后面接触其他双指针题都会很顺畅。最后分享一个小习惯我在面试手写这类题时一定会在代码里把ans的更新写在收缩之前因为这是整段代码里唯一一个顺序错了也不会编译报错、只会跑出错误答案的地方先写对它再谈其他优化。