开头刷 LeetCode 的朋友应该都有这种体验一道题看名字觉得很简单真正动手一写才发现坑全在细节里。力扣 209 题“长度最小的子数组”就是典型代表它挂着“中等难度”的标签但几乎每个面试算法合集里都会出现因为它背后考察的滑动窗口思想是处理连续子数组问题的基石。这道题的核心需求很直白在一个正整数数组里找到和大于等于目标值的最短连续子数组返回它的长度。但真正难的不是读懂题而是如何在 O(n) 时间内把答案算出来同时把边界条件处理干净。这篇文章我会从暴力枚举开始拆带你理解为什么滑动窗口是正解再给出前缀和加二分的进阶思路最后把我在实际刷题和面试中踩过的坑、总结的排查方法全部分享出来。不管你是刚接触算法的新手还是准备面试想快速复习的工程师这篇都能给你一套能直接用的解题模板。1. 题目解读与核心思路拆解1.1 题目到底在问什么先原封不动看下题目描述给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和大于等于 target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。关键信息有三个数组元素是正整数要找的是连续子数组并且要求“长度最小”。这三个条件决定了整个解题方向。正整数意味着数组单调递增求和时不会出现负数这为滑动窗口的可行性提供了前提连续子数组意味着我们不能像处理子序列那样随意跳选长度最小则是一个典型的优化目标不是“有没有”而是“最短多少”。很多初学者会下意识想到排序但这里数组的原始顺序必须保留因为子数组强调连续性一旦排序就破坏了位置关系。所以这道题本质上是在一个固定顺序的序列上做区间搜索所有解法都要围绕“区间”来思考。举个例子数组是 [2,3,1,2,4,3]target 是 7。肉眼扫一遍[4,3] 的和是 7长度 2这就是答案。但程序可没有肉眼它需要一种系统性的搜索方式要么枚举所有区间要么利用某种机制加速。1.2 暴力枚举为什么慢以及优化的方向暴力思路很直接用两层循环固定区间的左端点和右端点计算区间和如果满足条件就更新最小长度。这样做的复杂度是 O(n^2)在 n 达到 10^5 级别时就会超时。但注意这还不是最差的如果每次都用循环重新求和复杂度会退化到 O(n^3)。所以至少要先用前缀和把区间和优化到 O(1) 查询暴力才能勉强跑到 O(n^2)。为什么暴力慢因为它做了大量重复计算。比如左端点 i 固定时右端点 j 从 i 一直移到末尾每次移动都要重新计算 sum(i, j)。当你把左端点移到 i1 时很多区间和又要重新算一遍。这些重复正是我们可以优化的空间。优化的核心观察是由于所有元素都是正整数当右端点固定时随着左端点向右移动区间和是递减的当左端点固定时随着右端点向右移动区间和是递增的。这种单调性给了我们两种思路第一种思路是滑动窗口维护一个左指针和一个右指针右指针负责扩展区间当区间和达标后左指针尝试收缩窗口不断更新最小长度。因为指针只向右移动每个元素最多被访问两次复杂度是 O(n)。第二种思路是前缀和加二分前缀和数组本身是严格递增的因为正整数对于每个左端点我们可以用二分查找找到第一个使得前缀和之差大于等于 target 的右端点复杂度是 O(n log n)虽然不如滑动窗口但代码的数学味道更浓面试时可以作为替代方案展示。这两种思路的本质都是利用了“正整数数组”带来的单调性。如果数组里有负数滑动窗口就会失效因为窗口和不是单调变化的。这也是面试官喜欢追问的点如果数组包含负数你会怎么做答案往往要转换成前缀和加哈希表类似“和为 K 的子数组”那题的思路。不过那是后话先把今天这题吃透。2. 滑动窗口解法从原理到代码实现2.1 滑动窗口的经典套路滑动窗口不是一个抽象的概念它就像一个可以伸缩的尺子。你先把尺子的右端向右拉让窗口覆盖更多元素直到窗口内的和超过 target然后你开始慢慢收紧尺子的左端看能不能在保持和大于等于 target 的情况下把窗口缩短。每次收缩成功就记录当前窗口的长度。重复这个过程直到右端到达数组末尾。这套流程的学名叫“双指针”但更形象的叫法是“滑动窗口”。它要求窗口的滑动方向是一致的即左右指针都只向右移动不会回头。之所以能这样是因为数组是正数右指针向右扩展时和必然增加左指针向右收缩时和必然减少。这种单调性保证了我们不需要回退指针就能穷举所有可能的“最佳窗口”。具体到实现你可以这样想初始化左指针 left0窗口和 sum0最小长度 result无穷大。让右指针 right 从 0 到 n-1 遍历每次把 nums[right] 加进 sum。只要 sum 大于等于 target说明当前窗口满足条件。这时尝试更新 resultmin(result, right-left1)然后把 nums[left] 从 sum 中减掉同时 left 向右移动一位。这一步是在收缩窗口意图是看看能不能用更短的长度也能满足条件。重复步骤 3直到 sum 再次小于 target然后继续移动右指针。这里有个很多人会踩的误区在步骤 3 中为什么用 while 而不是 if因为收缩一次后可能窗口仍然满足条件。比如窗口 [1,2,3] 的和是 6target 是 5收缩左端后变成 [2,3]和是 5依然满足。你需要一直收缩到不满足为止才能保证不会漏掉更短的答案。所以必须用 while。另外result 应该初始化为多少常见做法是初始化为 n1 或者一个很大的数比如 nums.size()1。因为最终答案最大就是 n如果最后 result 还是 n1说明没找到任何满足条件的子数组返回 0。2.2 代码实现与细节讲解用 C 写一遍代码非常简洁class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int left 0; int sum 0; int result n 1; // 初始化为不可能的最大值 for (int right 0; right n; right) { sum nums[right]; while (sum target) { result min(result, right - left 1); sum - nums[left]; left; } } return result n 1 ? 0 : result; } };如果换成 Python写法几乎一样def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) left 0 total 0 result n 1 for right in range(n): total nums[right] while total target: result min(result, right - left 1) total - nums[left] left 1 return 0 if result n 1 else result这段代码看起来简单但里面的细节值得逐行拆。先看循环顺序外层的 for 循环固定了右指针内层的 while 处理左指针的收缩。右指针每前进一步就尝试“消化”当前满足条件的窗口。你可能会有疑问为什么不在 while 里也移动 right因为 right 的移动是主流程如果 while 里动 right会打乱遍历顺序。滑动窗口的标准写法就是外层扩展右边界内层收缩左边界两者职责分明。再看不满足条件的情况如果整个数组的和都小于 target那么 while 永远不会进入result 就会停留在初始值 n1最后返回 0。这个逻辑写起来很方便但不能用 result 初始化为 0 再最后判断因为 0 也可能是一个合法答案吗不是题目要求最小长度至少为 1但用 n1 作为哨兵更安全因为当 target 刚好等于某个元素窗口长度可能是 1此时 result 更新为 1不会和哨兵混淆。还有一个细节sum 的类型。题目给出的是正整数数组数组长度可能很大比如 10^5每个元素最大 10^5总和可能达到 10^10超过了 int 的表示范围32 位 int 最大值约 2.1e9)。所以 C 里最好用 long long 来存 sum。虽然 LeetCode 官方测试数据有时候 int 不会爆但自己写的时候养成好习惯别让类型溢出成为隐患。2.3 复杂度分析与正确性证明时间复杂度方面右指针从头到尾移动 n 次左指针最多也移动 n 次因为 left 只增不减所以两个指针的总移动次数不超过 2n复杂度是 O(n)。空间复杂度只用了一个 sum 变量和两个指针O(1)。正确性证明是面试中可能被要求的。我们需说明为什么右指针右移、左指针右移这种方式不会漏掉最短窗口核心是“单调性”。假设存在一个最优窗口 [L, R]它的和正好大于等于 target且长度最短。我们的算法会遍历所有 right 作为右端点当 right 到达 R 时由于右指针之前一直在移动left 可能停在某个小于等于 L 的位置。这时窗口 [left, R] 的和一定大于等于 [L, R] 的和因为 left L窗口里多包含了 L 之前的若干正数所以 sum target。于是 while 循环会触发收缩left 会一直向右移动直到 sum target。在这个过程中left 必然会经过 L 这个位置。当 left 等于 L、right 等于 R 时窗口正好是最优窗口result 会被更新为 R-L1。所以算法不会漏掉最优解。更严谨的说法是对于任何左端点 i右端点 j 是满足条件的最小右端点。因为窗口左端不断收缩右端不断扩展每个 i 最多被考虑一次且 j 是从小到大单调的所以能覆盖所有候选窗口。这个过程可以形象理解为“用一根橡皮筋从左到右捻过整个数组每个位置都被橡皮筋的两端扫过一遍”。3. 前缀和加二分查找另一种优雅解法3.1 前缀和数组的构造如果你面试时已经熟练使用滑动窗口那这题基本够用了。但有些面试官会故意让你“换个思路”或者在追问中暗示你使用二分。这时候前缀和加二分就是你的第二张牌。前缀和数组 preSum 的定义是preSum[i] 表示原数组 nums 前 i 个元素的和特别地preSum[0]0。这样区间 [i, j]注意这里的 i、j 是下标区间含左端不含右端或者用闭区间对应关系不同写法要小心的和可以表示为 preSum[j1] - preSum[i]。举个例子nums[2,3,1,2,4,3]preSum[0]0preSum[1]2preSum[2]5preSum[3]6preSum[4]8preSum[5]12preSum[6]15。要计算 nums[2..4] 的和就是 preSum[5]-preSum[2]12-57。为什么要用前缀和因为它把区间和转化为两个前缀和的差而 preSum 数组是严格递增的因为 nums 全是正数。严格递增意味着我们可以用二分查找来快速定位。具体到本题的解法我们枚举左端点 i希望找到一个最小的右端点 jj i使得 preSum[j1] - preSum[i] target即 preSum[j1] preSum[i] target。由于 preSum 递增可以在 preSum 数组上用 lower_bound 找到第一个大于等于 preSum[i]target 的位置。这里下标映射很容易晕。假设 lower_bound 返回的位置是 pos那么 pos 对应的是 preSum 的下标它等于原数组右端点下标加 1所以子数组长度就是 pos - i。因为 preSum 的下标范围是 0..n原数组下标范围是 0..n-1。比如 preSum[4] 对应的是 nums[0..3] 的和pos4 表示右端点是 nums[3]。3.2 二分查找的配合与边界处理先看代码C 版本如下class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); vectorlong long preSum(n 1, 0); for (int i 0; i n; i) { preSum[i 1] preSum[i] nums[i]; } int result n 1; for (int i 0; i n; i) { long long need preSum[i] target; // 需要达到的边界 auto it lower_bound(preSum.begin() i, preSum.end(), need); if (it ! preSum.end()) { int pos it - preSum.begin(); result min(result, pos - i); } } return result n 1 ? 0 : result; } };注意几个关键点。第一外层循环的 i 取值范围是 0 到 n。因为 preSum 有 n1 个元素我们枚举的是子数组的左边界前一个位置即 preSum 的下标。当 in 时preSum[i] 是全部元素的和如果这个和都不够 target那后面也没有元素了lower_bound 也不会找到结果所以循环到 n 没毛病。但实际可以优化到只循环 i n-1因为 in 时子数组不存在长度也为 0不会更新 result。第二lower_bound 的搜索范围要从 preSum.begin() i 开始为什么不能从 begin() 开始因为要求子数组左端点是 i右端点必须大于等于 i所以 preSum 的查找起点必须是 i。如果从开头找可能会找到一个位置在 i 左边那就构成负长度区间了虽然 preSum[i] 是递增的lower_bound 找到的位置天然不会小于 i因为 needpreSum[i]所以从 begin()i 开始只是语义更清晰实际上从 begin() 开始也能找到正确位置。这里建议写清楚面试时解释起来也顺。第三当 lower_bound 返回 preSum.end() 时说明从当前左端点开始右侧所有元素加起来的和都不够 target那么再往后的左端点更不可能够因为丢掉了前面的正数但循环不会提前 break只是 end() 不会被计入逻辑上没问题。实际代码可以加一个简单的优化如果 last 前缀和 - preSum[i] target可以直接跳出循环因为后面的更小。Python 版用 bisect 也很方便from bisect import bisect_left def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) pre [0] for x in nums: pre.append(pre[-1] x) result n 1 for i in range(len(pre)): need pre[i] target pos bisect_left(pre, need, i, len(pre)) if pos len(pre): result min(result, pos - i) return 0 if result n 1 else result复杂度方面外层循环 n1 次每次二分 O(log n)总复杂度 O(n log n)。虽然比滑动窗口慢但在 n 小于 10^5 时完全够用而且这种解法更容易扩展“最小平均子数组”一类的问题所以值得储备。3.3 两种解法对比从实际刷题角度看滑动窗口是这道题的最优解时间 O(n)代码短面试中最推荐优先写出。前缀和加二分可以作为“如果被要求给出另一种解法”的备选或者当你第一反应没想到滑动窗口时用前缀和也能稳过。两者对比如下解法时间复杂度空间复杂度代码量适用场景滑动窗口O(n)O(1)很短数组全为正数且目标是区间和前缀和二分O(n log n)O(n)中等数组全为正数需要可解释的数学思路前提条件是数组元素为正数。如果数组有负数滑动窗口的收缩条件就崩了因为窗口和不再随着 left 移动而单调递减right 移动时也不能保证窗口和单调递增。这时候就要考虑前缀和配合其他结构比如“和为 K 的子数组”那题的哈希表优化。所以你会发现同一个解法能否成立完全取决于题目给的约束条件。刷题时多问自己一步“这个解法依赖了什么性质如果性质被破坏还能用吗”这比背模板重要得多。4. 实操过程中的常见问题与排查技巧4.1 边界条件翻车现场我第一次写这题的时候把 while 写成 if结果在 target 较小的用例上直接崩了。比如 nums[1,1,1,1]target2当 right1 时sum2if 进去更新长度 2然后 left 加一sum 变成 1循环退出。但此时窗口 [1,1] 已经不满足条件了正确做法是继续收缩不对这里因为 left 收缩后窗口不满足所以 if 和 while 结果相同。但换一个用例 nums[2,3,1,2]target7right2 时 sum6 不满足right3 时 sum8 满足if 进去更新长度 4left 加一变为 1sum6循环退出。可实际上窗口 [3,1,2] 也就是 nums[1..3] 的和是 6还不满足但 [1,2] 更短也不满足看起来没有漏。再试 nums[1,2,3,2,4]target7。right2 时 sum6 7right3 时 sum8 7if 更新长度 4left1sum7窗口 [2,3,2]此时 sum 仍 7如果只用 if就会退出下次 right4 时 sum11但窗口 [3,2,4] 的长度是 3不是最优最优其实是 [2,4] 长度 2nums[3] 是 2我写错了应该测试下。总之只用 if 会错过连续收缩后依然满足的情况一旦出现就会漏掉更短的窗口。所以必须用 while。另一个坑是 result 的初始值。如果初始化为 0最后判断 result0 返回 0会因为 target 可能等于某个单个元素比如 nums[1,2,3]target3正确答案是 1但此时 result 会被更新为 1不会出现 0 混淆。但如果 target 恰好没有答案result 保持 0返回 0 也是对的。不过用 n1 更自然因为 0 通常被误解为“没有答案”而题目中长度为 0 是没有意义的。4.2 如何快速验证正确性刷题时我会先写完代码再用几个极端用例自测。第一个用例是空数组nums[]target5直接返回 0。滑动窗口代码里 n0for 循环不执行result 保持 1返回 0没问题。但要注意如果代码里直接访问 nums[right] 时没有检查 n下标会越界所以一定要先处理 n0。第二个用例是单元素数组nums[5]target5窗口长度 1直接 while 进入更新 result1然后 left 变成 1循环结束返回 1。如果 target6sum 始终不到 6返回 0。第三个用例是整个数组刚好满足比如 nums[1,2,3], target6正确答案是 3。代码运行 right0,1,2 累计 6while 进入更新长度 3left 移到 1sum5 退出返回 3。没问题。第四个用例是最优窗口在中间比如前面举过的 [2,3,1,2,4,3], target7答案 2。手推一下right 从 0 累计直到 right4 时 sum12while 收缩 left先更新长度 5left1,sum10更新长度 4left2,sum7更新长度 3left3,sum4因为 nums[2]1 被移走sum7 退出。right5 时 sum7加上 nums[5]3while 进入更新长度 3窗口 [2,4,3]? 等一下 left3 到 right5 是 [2,4,3] 长度 3然后 left4,sum4退出不对我写乱了。人工验证可能麻烦可以用打印调试。我建议刷题时写个简单的测试框架把暴力解和滑动窗口放在一起跑随机样例对比结果。这个习惯很管用能快速暴露边界问题。4.3 面试现场怎么答面试遇到这道题我一般会先花 20 秒和面试官确认约束“题目说的是正整数数组对吗如果元素有负数解法要变。”然后先说暴力思路再自然过渡到滑动窗口。哪怕你一眼能看出最优解也要把思考过程展现出来这比直接甩代码加分。讲滑动窗口时我会画一个数组的简单示意图用两个下标表示窗口说明右指针负责“找可行解”左指针负责“优化可行解”。然后强调单调性是能这样移动的前提“因为全是正数窗口和随 left 右移而减小随 right 右移而增大所以不存在需要回头的情况。”代码写完后主动分析复杂度然后补充一句“如果面试官想听更数学的版本我还可以用前缀和加二分时间复杂度 O(n log n)空间 O(n)。”这能展示你的知识广度。最后别忘了说边界条件n 为 0 返回 0找不到返回 0。另外有个小细节面试官可能会追问“如果 target 非常大超过数组总和你的代码会怎样”回答是滑动窗口的 while 永远不会进入result 保持 n1最终返回 0前缀和解法 lower_bound 会返回 end()也返回 0。这种追问的目的通常是想看你能不能说出返回条件提前想好代码里的哨兵值就不会卡壳。5. 延伸思考从这道题看算法思维5.1 滑动窗口的适用场景滑动窗口不是一个孤立的算法而是一类题的通用解法。它的适用条件可以总结为两条一是求解目标与“连续区间”有关二是窗口在扩展和收缩时目标值具有单调性。满足这两个条件滑动窗口往往就是最优解。常见的变体有“无重复字符的最长子串”LeetCode 3、“最大连续1的个数 III”LeetCode 1004、“替换后的最长重复字符”LeetCode 424等。它们的核心都是维护一个窗口通过调整左右指针来满足某种约束。区别在于约束的判断方式有的用哈希表记录字符频次有的用计数变量但外层骨架几乎一致。碰到这类题我会先思考窗口代表什么右指针扩展会带来什么影响左指针收缩会带来什么影响什么时候窗口是合法的什么时候需要收缩把四个问题理清楚代码自然就出来了。5.2 类似题目串讲如果把本题的“正整数数组”改成“有正有负的数组”滑动窗口就不能用了。因为窗口和不再单调收缩左边可能让和变大也可能变小。这时候求“和大于等于 target 的最短子数组”就变成一个更复杂的问题通常需要借助前缀和并维护某种有序结构。但如果只求“和为 target 的子数组个数”那就是另一道经典题——LeetCode 560。那道题用前缀和加哈希表时间复杂度 O(n)空间 O(n)。核心公式是当遍历到位置 j 时我们想知道有多少个 i 使得 preSum[j] - preSum[i] target也就是 preSum[i] preSum[j] - target。用哈希表存前缀和出现的次数即可。对比一下209 的“大于等于”和 560 的“等于”一字之差解法天差地别。前者因为“大于等于”有单调性可以用滑动窗口后者因为“等于”需要精确匹配滑动窗口无法判断收缩方向除非数组全是正数。这个对比能帮你理解为什么题目对数组元素的限制如此关键。还有一道“子数组最大平均数 I”LeetCode 643固定窗口大小要求窗口平均值最大。那种题是定长滑动窗口用固定大小维护窗口和本质上也是双指针只是窗口大小不变。滑动窗口可以根据“是否定长”分成两类解题时先判断窗口是否定长再决定是否需要在扩展后固定收缩。5.3 个人经验与建议我个人刷了三百多道题之后最大的体会是不要急着看题解先自己推一遍暴力解法再尝试找优化点。比如 209 这题暴力很好写写完后你自然会觉得“咦为什么每次都要重复求和”这时候再引入前缀和或双指针逻辑就顺理成章了。如果一上来就背滑动窗口模板遇到变种题很容易漏掉“单调性”这个根本条件。在实际编码中我还会刻意练习“边写边小声讲思路”这能帮助我在面试时保持清晰表达。你会发现当你能把“为什么要用 while 收缩”“为什么 left 只增不减”“为什么 result 初值设为 n1”都讲明白时代码已经不可能写错了。最后分享一个我自己做题的小工具对于这种双指针题我会写一个自动测试脚本用暴力解法和优化解法同时跑一批随机生成的测试数据如果结果不一致就打印出错时数组和 target。这样能快速定位到特殊用例比用 LeetCode 提交一次等反馈快得多。这道题我当年就是这样验证了自己的滑动窗口写法——在一次随机数据里因为 C 的 int 类型溢出暴力解和滑动窗口结果不一样排查了半天才发现是变量类型的问题。从那以后只要涉及累加我第一反应就是 long long这也是今天文章里反复强调类型细节的原因。顺便说一句如果你刚开始刷题遇到“长度最小”“最长子串”“窗口内最大值”这类关键词脑子里可以跳出两个候选方向一是滑动窗口二是单调队列/哈希表辅助。先把最简单的滑动窗口练熟再用题目中的约束条件判断它是否成立。209 题就是练手的最佳开胃菜搞定它后面一连串滑动窗口题都会顺畅很多。