力扣209题——长度最小的子数组——基本上是我拿滑动窗口考候选人时的默认开场题。题目本身不复杂给定一个全是正整数的数组 nums 和一个正整数 target找出数组中满足其和 ≥ target 的连续子数组的最短长度如果不存在就返回 0。这道题在力扣标签里是滑动窗口、前缀和的经典题也是力扣热题 100和许多大厂面试题库里的标配。它考察的东西很纯粹你懂不懂双指针向右移动时的状态维护懂不懂什么时候扩、什么时候缩、缩了之后发生了什么。我把话放在这里能把这道题一次写对并讲清楚的人滑动窗口的基本功基本是过关的。这篇文章我会从题目本身的边界条件讲起手推滑动窗口的每一步再给出前缀和二分的另一套写法最后盘点面试官最常追问的变体和真实调试中会遇到的坑。1. 先把题意嚼碎边界条件与隐藏陷阱1.1 题目到底在说什么我刷题这些年见过太多人在 209 上差点对了——样例过了一交就挂。原因多半不是不会滑动窗口而是没有把题目条件真正读透。先看原题给的条件nums 数组里的元素是正整数target 也是正整数。这两个词不是随便写的它是整个算法能够用滑动窗口的前提。为什么因为当所有元素都是正数时窗口的和是随着右端点向右移动严格单调不减的。说人话就是你把窗口右边往右拖总和只会变大不会变小你把窗口左边往右收总和只会变小不会变大。这个单调性就是我们敢用双指针收缩窗口的底气。注意题目要求的是连续子数组。连续意味着你不能排序、不能跳着选只能盯着相邻的一段。很多人在面试时我说如果允许你打乱顺序重新选你怎么做他们往往急着回答先排序我先不点破因为那道题就成贪心了和 209 考的不是一回事。至于为什么排序在这里是错的后面变体部分再说。还有一个容易被忽略的本题关键题目只要求和 ≥ target并不要求和恰好等于 target。这意味着条件满足之后你还要继续尝试缩短长度而不是停下来。很多第一次写这道题的人在 window_sum 第一次超过 target 时就直接 return 了这是典型的理解偏差——你要找的是最短不是第一个。1.2 例子里藏着的答案力扣官方给的例子是 nums [2,3,1,2,4,3]target 7。我们来手动推一遍这个推演过程面试时经常用来考察你的表达。从头开始看最短的答案是 2也就是 [4,3] 这一段和是 7长度 2。有没有更短的长度 1 的子数组里最大只有 4够不到 7所以 2 就是正确答案。这里要注意一个细节不是所有连续子数组都从下标 0 开始很多新手上来就固定左边界只移动右边界那样求的是从某个位置开始的最短长度而不是全局最短会漏解。再想一层为什么 [2,3,1,2] 这一段和是 8满足条件却不被选中因为它的长度是 4太大了。真正的最优解往往出现在刚刚够到 target 但又没有富余的窗口上。这也是为什么滑动窗口要找的是窗口和从 ≥ target 收缩到刚好 target 的瞬间——那个瞬间记录的 right - left 1才是以当前 right 为结尾的最短候选长度。1.3 暴力解法为什么必挂先不说最优解我们先算一下暴力解的账。最直接的思路是枚举左端点 i枚举右端点 j计算 sum(i..j)找到所有满足和 ≥ target 的区间里最短的一个。三层循环的复杂度是 O(n^3)肯定不行稍微优化一点枚举左右端点用前缀和 O(1) 算区间和复杂度降到 O(n^2)在 n 10^5 的规模下依然超时。面试时如果你一上来就说 O(n^2) 的枚举不丢人但一定要能自己指出问题n 最大 10^5O(n^2) 是 10^10 量级显然不可行。 这句话本身就是加分项说明你有复杂度意识。那 O(n^2) 为什么可以优化因为所有数是正的窗口右边界往前走和只增不减所以左边界可以在右边界移动的过程中只往右走、永不回头这就是滑动窗口能到 O(n) 的根本原因。说白了暴力解浪费在重复计算了大量不可能成为最优解的区间上而滑动窗口用单调性把这些区间直接剪掉了。2. 滑动窗口为什么它是最优解2.1 窗口的扩与缩到底怎么操作滑动窗口的实现其实就四步右指针 right 从 0 到 n-1 依次把 nums[right] 加进窗口和 window_sum 里这一步叫扩。只要 window_sum ≥ target说明当前窗口已经满足条件就用 right - left 1 更新答案。然后进入 while 循环不断把 nums[left] 从 window_sum 里减掉同时 left 右移这一步叫缩。直到 window_sum target跳出 while右指针继续往前走。核心思想是以 right 结尾的所有满足条件的子数组里我们只关心最靠右的那个 left因为 left 越靠右长度越短。一旦 left 不能再往右缩了再缩就 target 了说明以当前 right 为结尾的最短窗口已经找到right 继续向右走尝试寻找更短的可能性。这个过程里 left 不可能回退。为什么因为如果某个 left 位置曾经导致 window_sum ≥ target那之后 window_sum 只会随着 left 右移继续减小任何更靠左的 left 不会给后面的 right 带来更短的窗口所以 left 一直往右走是安全的。这就是双指针能做到 O(n) 的数学依据也是整道题最核心的一句话left 永不回头。2.2 正确性的直觉证明有人可能会问你 right 向右走窗口总和变大以前满足条件的 left 现在可能更满足条件你怎么能确定更新答案后就立刻 left 右移是对的呢关键是最短长度这个目标。当 right 固定时假设 left 从最左边开始右移window_sum 单调下降一旦它第一次降到 target 以下此时 left 再往右任何一个位置都不可能满足和 ≥ target所以对于这个 right我们已经尝试到了所有可能的 left当前记录下的 right - left 1 就是以 right 为结尾的最短长度。right 递增遍历所有可能的右端点全局最小值就出来了。这个思路在面试里我会建议你用白板画一个数轴把 left 和 right 的位置动态标出来顺便写一句窗口和 ≥ target 时收缩左边界的断言讲起来比背代码清楚得多。面试官最想听到的其实就是你能把为什么 left 不会错过正确答案说透。2.3 时间复杂度与空间复杂度滑动窗口只有一个 for 循环加一个 while 循环。有人一看到 while 套 for 就说 O(n^2)这是错的。left 和 right 各自最多移动 n 次每个元素最多被加进窗口一次、被移出窗口一次总操作次数是 2n 量级所以时间复杂度 O(n)空间复杂度 O(1)不额外开数组。面试时能讲出这个每个元素至多进出各一次的人比单纯背结论的人强很多。因为这句话直接回答了面试官的经典追问为什么内层有 while 还是 O(n) 你只要把 left 和 right 的移动次数上限摆出来这个问题就结束了。同理这道题也适合用来引入摊还分析的思想看似内层循环但总成本均摊到每个元素上是常数级。3. 两种主流实现与代码细节3.1 标准滑动窗口代码Python 版本def min_sub_array_len(target: int, nums: list[int]) - int: n len(nums) ans n 1 left 0 window_sum 0 for right in range(n): window_sum nums[right] while window_sum target: ans min(ans, right - left 1) window_sum - nums[left] left 1 return ans if ans ! n 1 else 0C 版本class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int ans n 1; int left 0, sum 0; for (int right 0; right n; right) { sum nums[right]; while (sum target) { ans min(ans, right - left 1); sum - nums[left]; } } return ans n 1 ? 0 : ans; } };有个小细节值得提ans 初始值是 n1而不是 n。如果整个数组的和都小于 target答案应该是 0如果初始为 n最后返回 ans n 就会把没找到和恰好整个数组长度混在一起逻辑就脏了。设成 n1 可以非常干净地判断是否找到过这个习惯我用到现在几乎所有滑窗题都沿用了。再解释一下 right - left 1 为什么是这个式子right 是从 0 开始的下标left 也是从 0 开始的下标二者之差是间隔的元素个数减一所以区间长度要再加一。比如 right 4, left 3中间只有 nums[3] 和 nums[4] 两个元素长度是 4 - 3 1 2。这个运算看起来简单但在边界条件稍微复杂的题目里非常容易出错我建议每次写完都心里代入一个单元素区间验证一下。3.2 前缀和二分另一条路滑动窗口已经 O(n)为什么还要学前缀和二分两个原因一是面试官可能会要求你换一种解法二是遇到数组里有负数的情况比如力扣 862滑窗会失效前缀和那套思想是继续解题的基石。前缀和数组 pre[i] 表示原数组前 i 个元素之和pre[0] 0。因为原数组全为正数pre 是严格递增的。对每个右端点 i从 1 到 n我们希望找到一个尽量靠右的下标 j使得 pre[i] - pre[j] ≥ target这样一来子数组 [j1, i] 的长度 i - j 就是候选答案。变形一下pre[j] ≤ pre[i] - target。因为 pre 递增所以可以用二分在 pre[0..i-1] 里找最后一个 ≤ pre[i] - target 的位置。Python 用 bisect_right 很顺手import bisect def min_sub_array_len(target: int, nums: list[int]) - int: n len(nums) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] nums[i] ans n 1 for i in range(1, n 1): limit pre[i] - target # 在 pre[0..i-1] 中找最后一个 limit 的下标 j bisect.bisect_right(pre, limit, 0, i) - 1 if j 0: ans min(ans, i - j) return ans if ans ! n 1 else 0C 里对应的是 upper_boundclass Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long pre(n 1, 0); for (int i 0; i n; i) pre[i 1] pre[i] nums[i]; int ans n 1; for (int i 1; i n; i) { long long limit pre[i] - target; auto it upper_bound(pre.begin(), pre.begin() i, limit); int j int(it - pre.begin()) - 1; if (j 0) ans min(ans, i - j); } return ans n 1 ? 0 : ans; } };解释一下 upper_bound 的语义它在 [pre.begin(), pre.begin() i) 里返回第一个大于 limit 的迭代器减一才是最后一个不大于 limit 的位置。这里 pre 数组用 long long是因为 pre[i] - target 在极端情况下可能超过 int 范围前缀和累加到很大时 C 里不用 long long 很容易吃大亏。这个版本的时间复杂度是 O(n log n)空间 O(n)。虽然比滑窗慢但它的价值在于递增数组上做二分这个思路可以推广到很多区间问题上。你用 nums [2,3,1,2,4,3], target 7 手推一遍pre [0,2,5,6,8,12,15]i4 时 limit 1二分找到 pre[0] 0j 0长度 4i5 时 limit 5pre[0..4] 里最后一个 ≤ 5 的是 pre[2] 5j 2长度 3对应 [2,4]i6 时 limit 8pre[0..5] 里最后一个 ≤ 8 的是 pre[4] 8j 4长度 2对应 [4,3]。推完就清楚多了。3.3 两种方法面试怎么选我的建议是优先写滑动窗口因为它是这道题的官方正解代码短、常数小、O(1) 空间面试官最想看到的就是这一版。写完滑窗之后主动补一句这题还可以用前缀和二分做复杂度 O(n log n)思路是在递增前缀和数组里二分查找如果时间允许可以画出前缀和数组演示一下这非常加分。给大家一个节奏参考拿到题先花 30 秒说思路再说一句话证明单调性然后直接写滑窗代码写完自己口算跑一遍例子最后主动报复杂度。这一套下来面试体验通常会明显好于那些闷头写代码的人。代码能不能跑对是一回事思路能不能讲清楚、边界能不能说全是另一回事而这些恰恰是 209 这道题真正想考察的。4. 面试官会怎么追问变体与答题话术4.1 如果数组里有负数还能用滑窗吗这是我最喜欢追问的问题之一。数组里一旦出现负数上面的单调性就没了右指针向右扩窗口和可能变小左指针向右缩窗口和可能变大。此时窗口和满足了就收缩的判断不再可靠滑动窗口直接失效。正确方向是换成前缀和单调队列这类题对应力扣 862和至少为 K 的最短非空子数组。思路是把问题转换成 pre[j] ≤ pre[i] - K为了快速找最小的 i-j需要维护一个下标和值都单调递增的双端队列。这道题难度直接上了一个台阶能在 209 的基础上想到这个方向说明你真的理解滑动窗口的适用边界。如果只是普通面试不一定要求现场推 862但你应该能说出负数会让单调性失效这一句这就把与普通候选人的差距拉开了。4.2 如果题目改成恰好等于 target怎么办至少变成恰好问题性质就不一样了。因为差值为 0前缀和可能重复不能单纯用滑窗窗口和会随着 left 右移失去单调对应关系最快的方式是前缀和哈希表遍历时用哈希表记录 pre[i] 的最近出现位置查找 pre[i] - target 是否出现过出现过就更新最短长度。这个变体也经常出现在面试中和 209 放一起对比考的就是你对差量查询的理解。不过这里要提醒一句如果数组仍全是正整数恰好等于其实也可以用双指针因为窗口和单调sum target 就右扩sum target 就左缩sum target 就记答案这是另一套判定逻辑。面试时先确认数组的正负性再决定用哪种方案这一问大概率是送分题。4.3 如果是求乘积小于 K 的子数组这是力扣 713 的变体和 209 几乎一个模子窗口内乘积小于 K求子数组个数或者最短长度。区别只在约束从和换成了乘积窗口虽然同样满足单调性全为正数时右扩乘积变大左缩乘积变小但乘法有个坑——乘积增长极快需要像 C 里用 long long 甚至提前退出。这一票变体都会在面试时大量出现能把 209 的滑窗框架吃透这些题基本就是换皮核心的扩-缩-更新答案三步完全一样。4.4 如果 nums 很大内存放不下怎么办这个追问考的是数据流场景。如果数组不能一次性全部加载比如数据来自一个只读流滑动窗口的优势就体现出来了你只需要维护当前窗口的和以及 left/right 两个下标不需要回头访问已经滑过的元素。如果你只写了前缀和二分那版在这个追问面前就会比较被动因为前缀和数组本身就和原数组一样大。所以这道题我建议优先掌握滑窗不只是因为复杂度更优还因为它更容易扩展到流式处理这种真实场景。5. 踩坑实录与调试技巧5.1 三个高频 Bug第一个 Bugans 初始值给成 n。当整个数组和都不够 target 时返回结果应该是 0但你拿到的是 n样例如果没覆盖全数组和不足这种用例就会悄悄挂掉。我建议统一用 n1 作为哨兵最后判断它有没有被更新过。第二个 Bugwhile 写成了 if。如果把只要满足和 ≥ target 就收缩写成 if每个右端点只会尝试收缩一次但真实场景里可能需要连续缩多次——比如窗口里有两个大数缩掉左边一个后窗口和依然 ≥ target此时必须继续缩。这个 bug 用 [1, 2, 3, 8], target 8 就能暴露用 if 你会得到长度 2[3,8]正确答案是 1[8]。第三个 Bug累加和溢出。在原题范围内不会发生但面试官如果随手把 target 改成很大的数或者让你处理大整数数组C 里建议把 window_sum 声明成 long long。这一类边界问题属于平时看不见一爆就是 WA提前预防比事后再调舒服很多。5.2 一个调试技巧把窗口状态打印出来我调试滑窗题有一个习惯在 while 循环里加一行临时输出打印 right、left、window_sum 和当前 ans。比如对 nums[2,3,1,2,4,3]、target7你会看到窗口是这样移动的right3 时 left0 累计和 8缩到 left1 和为 6right4 时和为 10缩到 left3 和为 6right5 时和为 9缩到 left4 和为 7得到长度 2。把这个手工推演过程写一遍能极大减少凭感觉写对但不知道哪里对的虚无感。打印调试看起来笨重但它在排查窗口为什么没缩答案为什么偏大这类问题时比任何静态分析都快。等窗口状态和你的手推逻辑完全一致了再把 print 删掉代码就是干净的。5.3 写完代码后建议做的四组测试第一组nums [1,1,1,1,1], target 6答案是 0测无解分支。 第二组nums [1,2,3,4,5], target 15答案是 5测整个数组刚好够。 第三组nums [5], target 5答案是 1测单元素。 第四组nums [1,1,1,1,1], target 1答案是 1测 target 很小但数组里就有单个满足的情况。这四组用例覆盖了没答案、刚好全数组、单元素、极值四种典型边界写完跑一遍比盲试更稳。我在面试别人时也很喜欢让候选人说出他准备怎么测能主动列出这类边界的基本功是可信的。5.4 关于前缀和二分的二分边界用 bisect_right 找最后一个 ≤ limit时搜索区间是 [0, i)不包括 i 自己因为子数组长度至少为 1。很多人在这个左闭右开区间上犯迷糊万一 limit 很大bisect_right 返回 i那 j i-1 正好是最后一个可行的位置长度 i - (i-1) 1没问题万一 limit 很小bisect_right 返回 0j -1说明连 pre[0] 都超了直接跳过。这个语义一旦想清楚二分版本就不容易写错。这道 209 题我每年都要见很多次说句实在的它非常能反映一个人的算法功底不是看你能不能背出滑动窗口模板而是看你能否当面试官改一个条件时立刻意识到哦单调性没了滑窗不成立了。我在实际带人时经常让大家用一个条件变三问的方式来练题把和 ≥ target改成和 ≤ target和 target数组含负数每改一次就重写一遍思路。这样练过之后再遇到 713、862、325 这类衍生题就会很从容。如果你也在刷力扣热题 100我的建议是别贪多把 209 这种骨架题吃透比盲目冲十道新题有效得多。
力扣209长度最小的子数组：滑动窗口与二分前缀和双解法详解
力扣209题——长度最小的子数组——基本上是我拿滑动窗口考候选人时的默认开场题。题目本身不复杂给定一个全是正整数的数组 nums 和一个正整数 target找出数组中满足其和 ≥ target 的连续子数组的最短长度如果不存在就返回 0。这道题在力扣标签里是滑动窗口、前缀和的经典题也是力扣热题 100和许多大厂面试题库里的标配。它考察的东西很纯粹你懂不懂双指针向右移动时的状态维护懂不懂什么时候扩、什么时候缩、缩了之后发生了什么。我把话放在这里能把这道题一次写对并讲清楚的人滑动窗口的基本功基本是过关的。这篇文章我会从题目本身的边界条件讲起手推滑动窗口的每一步再给出前缀和二分的另一套写法最后盘点面试官最常追问的变体和真实调试中会遇到的坑。1. 先把题意嚼碎边界条件与隐藏陷阱1.1 题目到底在说什么我刷题这些年见过太多人在 209 上差点对了——样例过了一交就挂。原因多半不是不会滑动窗口而是没有把题目条件真正读透。先看原题给的条件nums 数组里的元素是正整数target 也是正整数。这两个词不是随便写的它是整个算法能够用滑动窗口的前提。为什么因为当所有元素都是正数时窗口的和是随着右端点向右移动严格单调不减的。说人话就是你把窗口右边往右拖总和只会变大不会变小你把窗口左边往右收总和只会变小不会变大。这个单调性就是我们敢用双指针收缩窗口的底气。注意题目要求的是连续子数组。连续意味着你不能排序、不能跳着选只能盯着相邻的一段。很多人在面试时我说如果允许你打乱顺序重新选你怎么做他们往往急着回答先排序我先不点破因为那道题就成贪心了和 209 考的不是一回事。至于为什么排序在这里是错的后面变体部分再说。还有一个容易被忽略的本题关键题目只要求和 ≥ target并不要求和恰好等于 target。这意味着条件满足之后你还要继续尝试缩短长度而不是停下来。很多第一次写这道题的人在 window_sum 第一次超过 target 时就直接 return 了这是典型的理解偏差——你要找的是最短不是第一个。1.2 例子里藏着的答案力扣官方给的例子是 nums [2,3,1,2,4,3]target 7。我们来手动推一遍这个推演过程面试时经常用来考察你的表达。从头开始看最短的答案是 2也就是 [4,3] 这一段和是 7长度 2。有没有更短的长度 1 的子数组里最大只有 4够不到 7所以 2 就是正确答案。这里要注意一个细节不是所有连续子数组都从下标 0 开始很多新手上来就固定左边界只移动右边界那样求的是从某个位置开始的最短长度而不是全局最短会漏解。再想一层为什么 [2,3,1,2] 这一段和是 8满足条件却不被选中因为它的长度是 4太大了。真正的最优解往往出现在刚刚够到 target 但又没有富余的窗口上。这也是为什么滑动窗口要找的是窗口和从 ≥ target 收缩到刚好 target 的瞬间——那个瞬间记录的 right - left 1才是以当前 right 为结尾的最短候选长度。1.3 暴力解法为什么必挂先不说最优解我们先算一下暴力解的账。最直接的思路是枚举左端点 i枚举右端点 j计算 sum(i..j)找到所有满足和 ≥ target 的区间里最短的一个。三层循环的复杂度是 O(n^3)肯定不行稍微优化一点枚举左右端点用前缀和 O(1) 算区间和复杂度降到 O(n^2)在 n 10^5 的规模下依然超时。面试时如果你一上来就说 O(n^2) 的枚举不丢人但一定要能自己指出问题n 最大 10^5O(n^2) 是 10^10 量级显然不可行。 这句话本身就是加分项说明你有复杂度意识。那 O(n^2) 为什么可以优化因为所有数是正的窗口右边界往前走和只增不减所以左边界可以在右边界移动的过程中只往右走、永不回头这就是滑动窗口能到 O(n) 的根本原因。说白了暴力解浪费在重复计算了大量不可能成为最优解的区间上而滑动窗口用单调性把这些区间直接剪掉了。2. 滑动窗口为什么它是最优解2.1 窗口的扩与缩到底怎么操作滑动窗口的实现其实就四步右指针 right 从 0 到 n-1 依次把 nums[right] 加进窗口和 window_sum 里这一步叫扩。只要 window_sum ≥ target说明当前窗口已经满足条件就用 right - left 1 更新答案。然后进入 while 循环不断把 nums[left] 从 window_sum 里减掉同时 left 右移这一步叫缩。直到 window_sum target跳出 while右指针继续往前走。核心思想是以 right 结尾的所有满足条件的子数组里我们只关心最靠右的那个 left因为 left 越靠右长度越短。一旦 left 不能再往右缩了再缩就 target 了说明以当前 right 为结尾的最短窗口已经找到right 继续向右走尝试寻找更短的可能性。这个过程里 left 不可能回退。为什么因为如果某个 left 位置曾经导致 window_sum ≥ target那之后 window_sum 只会随着 left 右移继续减小任何更靠左的 left 不会给后面的 right 带来更短的窗口所以 left 一直往右走是安全的。这就是双指针能做到 O(n) 的数学依据也是整道题最核心的一句话left 永不回头。2.2 正确性的直觉证明有人可能会问你 right 向右走窗口总和变大以前满足条件的 left 现在可能更满足条件你怎么能确定更新答案后就立刻 left 右移是对的呢关键是最短长度这个目标。当 right 固定时假设 left 从最左边开始右移window_sum 单调下降一旦它第一次降到 target 以下此时 left 再往右任何一个位置都不可能满足和 ≥ target所以对于这个 right我们已经尝试到了所有可能的 left当前记录下的 right - left 1 就是以 right 为结尾的最短长度。right 递增遍历所有可能的右端点全局最小值就出来了。这个思路在面试里我会建议你用白板画一个数轴把 left 和 right 的位置动态标出来顺便写一句窗口和 ≥ target 时收缩左边界的断言讲起来比背代码清楚得多。面试官最想听到的其实就是你能把为什么 left 不会错过正确答案说透。2.3 时间复杂度与空间复杂度滑动窗口只有一个 for 循环加一个 while 循环。有人一看到 while 套 for 就说 O(n^2)这是错的。left 和 right 各自最多移动 n 次每个元素最多被加进窗口一次、被移出窗口一次总操作次数是 2n 量级所以时间复杂度 O(n)空间复杂度 O(1)不额外开数组。面试时能讲出这个每个元素至多进出各一次的人比单纯背结论的人强很多。因为这句话直接回答了面试官的经典追问为什么内层有 while 还是 O(n) 你只要把 left 和 right 的移动次数上限摆出来这个问题就结束了。同理这道题也适合用来引入摊还分析的思想看似内层循环但总成本均摊到每个元素上是常数级。3. 两种主流实现与代码细节3.1 标准滑动窗口代码Python 版本def min_sub_array_len(target: int, nums: list[int]) - int: n len(nums) ans n 1 left 0 window_sum 0 for right in range(n): window_sum nums[right] while window_sum target: ans min(ans, right - left 1) window_sum - nums[left] left 1 return ans if ans ! n 1 else 0C 版本class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int ans n 1; int left 0, sum 0; for (int right 0; right n; right) { sum nums[right]; while (sum target) { ans min(ans, right - left 1); sum - nums[left]; } } return ans n 1 ? 0 : ans; } };有个小细节值得提ans 初始值是 n1而不是 n。如果整个数组的和都小于 target答案应该是 0如果初始为 n最后返回 ans n 就会把没找到和恰好整个数组长度混在一起逻辑就脏了。设成 n1 可以非常干净地判断是否找到过这个习惯我用到现在几乎所有滑窗题都沿用了。再解释一下 right - left 1 为什么是这个式子right 是从 0 开始的下标left 也是从 0 开始的下标二者之差是间隔的元素个数减一所以区间长度要再加一。比如 right 4, left 3中间只有 nums[3] 和 nums[4] 两个元素长度是 4 - 3 1 2。这个运算看起来简单但在边界条件稍微复杂的题目里非常容易出错我建议每次写完都心里代入一个单元素区间验证一下。3.2 前缀和二分另一条路滑动窗口已经 O(n)为什么还要学前缀和二分两个原因一是面试官可能会要求你换一种解法二是遇到数组里有负数的情况比如力扣 862滑窗会失效前缀和那套思想是继续解题的基石。前缀和数组 pre[i] 表示原数组前 i 个元素之和pre[0] 0。因为原数组全为正数pre 是严格递增的。对每个右端点 i从 1 到 n我们希望找到一个尽量靠右的下标 j使得 pre[i] - pre[j] ≥ target这样一来子数组 [j1, i] 的长度 i - j 就是候选答案。变形一下pre[j] ≤ pre[i] - target。因为 pre 递增所以可以用二分在 pre[0..i-1] 里找最后一个 ≤ pre[i] - target 的位置。Python 用 bisect_right 很顺手import bisect def min_sub_array_len(target: int, nums: list[int]) - int: n len(nums) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] nums[i] ans n 1 for i in range(1, n 1): limit pre[i] - target # 在 pre[0..i-1] 中找最后一个 limit 的下标 j bisect.bisect_right(pre, limit, 0, i) - 1 if j 0: ans min(ans, i - j) return ans if ans ! n 1 else 0C 里对应的是 upper_boundclass Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long pre(n 1, 0); for (int i 0; i n; i) pre[i 1] pre[i] nums[i]; int ans n 1; for (int i 1; i n; i) { long long limit pre[i] - target; auto it upper_bound(pre.begin(), pre.begin() i, limit); int j int(it - pre.begin()) - 1; if (j 0) ans min(ans, i - j); } return ans n 1 ? 0 : ans; } };解释一下 upper_bound 的语义它在 [pre.begin(), pre.begin() i) 里返回第一个大于 limit 的迭代器减一才是最后一个不大于 limit 的位置。这里 pre 数组用 long long是因为 pre[i] - target 在极端情况下可能超过 int 范围前缀和累加到很大时 C 里不用 long long 很容易吃大亏。这个版本的时间复杂度是 O(n log n)空间 O(n)。虽然比滑窗慢但它的价值在于递增数组上做二分这个思路可以推广到很多区间问题上。你用 nums [2,3,1,2,4,3], target 7 手推一遍pre [0,2,5,6,8,12,15]i4 时 limit 1二分找到 pre[0] 0j 0长度 4i5 时 limit 5pre[0..4] 里最后一个 ≤ 5 的是 pre[2] 5j 2长度 3对应 [2,4]i6 时 limit 8pre[0..5] 里最后一个 ≤ 8 的是 pre[4] 8j 4长度 2对应 [4,3]。推完就清楚多了。3.3 两种方法面试怎么选我的建议是优先写滑动窗口因为它是这道题的官方正解代码短、常数小、O(1) 空间面试官最想看到的就是这一版。写完滑窗之后主动补一句这题还可以用前缀和二分做复杂度 O(n log n)思路是在递增前缀和数组里二分查找如果时间允许可以画出前缀和数组演示一下这非常加分。给大家一个节奏参考拿到题先花 30 秒说思路再说一句话证明单调性然后直接写滑窗代码写完自己口算跑一遍例子最后主动报复杂度。这一套下来面试体验通常会明显好于那些闷头写代码的人。代码能不能跑对是一回事思路能不能讲清楚、边界能不能说全是另一回事而这些恰恰是 209 这道题真正想考察的。4. 面试官会怎么追问变体与答题话术4.1 如果数组里有负数还能用滑窗吗这是我最喜欢追问的问题之一。数组里一旦出现负数上面的单调性就没了右指针向右扩窗口和可能变小左指针向右缩窗口和可能变大。此时窗口和满足了就收缩的判断不再可靠滑动窗口直接失效。正确方向是换成前缀和单调队列这类题对应力扣 862和至少为 K 的最短非空子数组。思路是把问题转换成 pre[j] ≤ pre[i] - K为了快速找最小的 i-j需要维护一个下标和值都单调递增的双端队列。这道题难度直接上了一个台阶能在 209 的基础上想到这个方向说明你真的理解滑动窗口的适用边界。如果只是普通面试不一定要求现场推 862但你应该能说出负数会让单调性失效这一句这就把与普通候选人的差距拉开了。4.2 如果题目改成恰好等于 target怎么办至少变成恰好问题性质就不一样了。因为差值为 0前缀和可能重复不能单纯用滑窗窗口和会随着 left 右移失去单调对应关系最快的方式是前缀和哈希表遍历时用哈希表记录 pre[i] 的最近出现位置查找 pre[i] - target 是否出现过出现过就更新最短长度。这个变体也经常出现在面试中和 209 放一起对比考的就是你对差量查询的理解。不过这里要提醒一句如果数组仍全是正整数恰好等于其实也可以用双指针因为窗口和单调sum target 就右扩sum target 就左缩sum target 就记答案这是另一套判定逻辑。面试时先确认数组的正负性再决定用哪种方案这一问大概率是送分题。4.3 如果是求乘积小于 K 的子数组这是力扣 713 的变体和 209 几乎一个模子窗口内乘积小于 K求子数组个数或者最短长度。区别只在约束从和换成了乘积窗口虽然同样满足单调性全为正数时右扩乘积变大左缩乘积变小但乘法有个坑——乘积增长极快需要像 C 里用 long long 甚至提前退出。这一票变体都会在面试时大量出现能把 209 的滑窗框架吃透这些题基本就是换皮核心的扩-缩-更新答案三步完全一样。4.4 如果 nums 很大内存放不下怎么办这个追问考的是数据流场景。如果数组不能一次性全部加载比如数据来自一个只读流滑动窗口的优势就体现出来了你只需要维护当前窗口的和以及 left/right 两个下标不需要回头访问已经滑过的元素。如果你只写了前缀和二分那版在这个追问面前就会比较被动因为前缀和数组本身就和原数组一样大。所以这道题我建议优先掌握滑窗不只是因为复杂度更优还因为它更容易扩展到流式处理这种真实场景。5. 踩坑实录与调试技巧5.1 三个高频 Bug第一个 Bugans 初始值给成 n。当整个数组和都不够 target 时返回结果应该是 0但你拿到的是 n样例如果没覆盖全数组和不足这种用例就会悄悄挂掉。我建议统一用 n1 作为哨兵最后判断它有没有被更新过。第二个 Bugwhile 写成了 if。如果把只要满足和 ≥ target 就收缩写成 if每个右端点只会尝试收缩一次但真实场景里可能需要连续缩多次——比如窗口里有两个大数缩掉左边一个后窗口和依然 ≥ target此时必须继续缩。这个 bug 用 [1, 2, 3, 8], target 8 就能暴露用 if 你会得到长度 2[3,8]正确答案是 1[8]。第三个 Bug累加和溢出。在原题范围内不会发生但面试官如果随手把 target 改成很大的数或者让你处理大整数数组C 里建议把 window_sum 声明成 long long。这一类边界问题属于平时看不见一爆就是 WA提前预防比事后再调舒服很多。5.2 一个调试技巧把窗口状态打印出来我调试滑窗题有一个习惯在 while 循环里加一行临时输出打印 right、left、window_sum 和当前 ans。比如对 nums[2,3,1,2,4,3]、target7你会看到窗口是这样移动的right3 时 left0 累计和 8缩到 left1 和为 6right4 时和为 10缩到 left3 和为 6right5 时和为 9缩到 left4 和为 7得到长度 2。把这个手工推演过程写一遍能极大减少凭感觉写对但不知道哪里对的虚无感。打印调试看起来笨重但它在排查窗口为什么没缩答案为什么偏大这类问题时比任何静态分析都快。等窗口状态和你的手推逻辑完全一致了再把 print 删掉代码就是干净的。5.3 写完代码后建议做的四组测试第一组nums [1,1,1,1,1], target 6答案是 0测无解分支。 第二组nums [1,2,3,4,5], target 15答案是 5测整个数组刚好够。 第三组nums [5], target 5答案是 1测单元素。 第四组nums [1,1,1,1,1], target 1答案是 1测 target 很小但数组里就有单个满足的情况。这四组用例覆盖了没答案、刚好全数组、单元素、极值四种典型边界写完跑一遍比盲试更稳。我在面试别人时也很喜欢让候选人说出他准备怎么测能主动列出这类边界的基本功是可信的。5.4 关于前缀和二分的二分边界用 bisect_right 找最后一个 ≤ limit时搜索区间是 [0, i)不包括 i 自己因为子数组长度至少为 1。很多人在这个左闭右开区间上犯迷糊万一 limit 很大bisect_right 返回 i那 j i-1 正好是最后一个可行的位置长度 i - (i-1) 1没问题万一 limit 很小bisect_right 返回 0j -1说明连 pre[0] 都超了直接跳过。这个语义一旦想清楚二分版本就不容易写错。这道 209 题我每年都要见很多次说句实在的它非常能反映一个人的算法功底不是看你能不能背出滑动窗口模板而是看你能否当面试官改一个条件时立刻意识到哦单调性没了滑窗不成立了。我在实际带人时经常让大家用一个条件变三问的方式来练题把和 ≥ target改成和 ≤ target和 target数组含负数每改一次就重写一遍思路。这样练过之后再遇到 713、862、325 这类衍生题就会很从容。如果你也在刷力扣热题 100我的建议是别贪多把 209 这种骨架题吃透比盲目冲十道新题有效得多。
