刷算法题刷到一定阶段你会发现有一类题特别有意思题目本身看起来非常简单甚至暴力解法一行就能说清楚但偏偏在面试里被反复问而且每次问都能挖出不同的层次。LeetCode 209题——长度最小的子数组就是这样的题目。它表面上是一个求子数组长度的问题实际上是滑动窗口技巧的经典入门题目同时也是考察边界处理、时间复杂度分析和思路演进的好素材。第一次做这道题的时候我的第一反应是“这么简单也能上209号题”结果写完暴力解法提交看到超时提示的那一瞬间才意识到这道题的考点根本不在于会不会求子数组和而在于能不能想到比暴力更优的解法。今天这篇文章就围绕这道题从暴力解法逐步演进到滑动窗口再补充前缀和加二分查找的进阶思路以及我刷这道题时踩过的几个典型坑。无论你是刚开始刷题的新手还是准备面试的老手这篇文章都会有一些值得看的内容。1. 把题目翻译成人话题目表面在问什么实际又在问什么1.1 题面拆解什么是长度最小的子数组题目原文是这样的给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和大于等于 target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。这里有几个关键信息需要拆开来看子数组必须是连续的不是子序列。这意味着你不能跳着选元素选定区间[i, j]后里面的所有元素都得算上。正整数这个条件非常关键。如果数组里有负数或零这道题的解法会完全不同因为窗口内累加和就不是单调的了。正因为全是正整数才可以用滑动窗口——窗口扩大时和一定增加窗口缩小时和一定减小这个单调性是整套算法的基石。大于等于 target不是等于 target。这个细节决定了窗口收缩的判断条件。举个例子nums [2,3,1,2,4,3]target 7那么满足条件的子数组有[3,1,2,4]长度为4、[4,3]长度为2、[2,3,1,2]长度为4等其中最短的是[4,3]长度是2。答案就是2。1.2 为什么这道题被归类为“滑动窗口”入门题滑动窗口这个技巧本质上是对暴力解法中大量重复计算的一种优化。暴力解法里我们要枚举所有可能的子数组起点和终点然后对每个子数组求和——这个求和过程是重复的。滑动窗口的核心思想是维护一个窗口通过不断调整左右边界在遍历过程中动态更新窗口内的和从而避免重复计算。从数据结构的角度看滑动窗口其实是一个双端队列的简化用法左端负责收缩右端负责扩张。而从思想层面看它是“单调性”在算法设计中的一次典型应用——因为有正整数这个约束窗口内的和才会随着窗口扩张而单调增加我们才能放心地收缩窗口。我个人的理解是这道题的价值不在于它本身有多难而在于它是理解后续一系列滑动窗口题目的“母题”。后面你遇到的字符串无重复字符的最长子串、水果成篮、最小覆盖子串本质上都是这个模板的变体。2. 从暴力解法出发知其慢才能知其所以快2.1 暴力枚举的思路与实现很多教程会直接跳过暴力解法直接讲滑动窗口。但我觉得理解暴力解法是理解滑动窗口必不可少的一步——你得先知道暴力解法慢在哪里才能体会滑动窗口到底优化了什么。暴力解法的思路非常直接枚举每个子数组的起点i然后从i开始逐步增加终点j每增加一个终点就计算一次子数组[i, j]的和一旦发现某个[i, j]的和大于等于 target就记录下当前长度并跳出内层循环。因为数组里全是正整数内层循环可以提前终止——从i往后和只会越加越大一旦满足条件继续往后加只会让长度更长没有意义。def minSubArrayLen(target, nums): n len(nums) ans n 1 # 初始化为一个不可能更大的值 for i in range(n): s 0 for j in range(i, n): s nums[j] if s target: ans min(ans, j - i 1) break return ans if ans ! n 1 else 0其实这里还有一个小优化每轮内层循环不必从i重新累加。我们可以先计算前缀和数组prefix然后用prefix[j] - prefix[i-1]来快速求出子数组和。这样内层循环的求和操作是常数的整体时间复杂度还是O(n^2)只是常数小了一些。2.2 暴力解法的性能瓶颈在哪里暴力解法最直观的问题是当数组很长时枚举的子数组数量是n(n1)/2个在 n 10^5 级别这是 LeetCode 上这类题目的典型数据规模时需要枚举大约 50 亿个子数组。即使每个子数组的和计算是常数时间这个规模也远远超出了 1 秒的限制。但暴力解法还有一个更隐蔽的浪费大量的求和是重复的。[i, j1]的和明明可以由[i, j]的和加上nums[j1]得到暴力解法却没有利用这个关系而是重新计算了窗口内的所有元素之和。我经常跟周围刷题的朋友说算法优化本质上就是“找重复”。暴力解法慢不是因为它笨而是因为它没有利用题目条件带来的性质——这里有两条性质可以利用数组全是正整数子数组和单调递增子数组的右边界移动时和的变化是增量式的。滑动窗口恰恰同时利用了两个性质用单调性保证窗口收缩的正确性用增量式计算保证和更新的效率。2.3 从暴力到滑动窗口的思维跃迁写暴力解法时你会有一个直观感受内层循环的起点一直在“回退”。比如第一轮枚举以nums[0]开头的所有子数组第二轮枚举以nums[1]开头的所有子数组——每一轮都把前面的工作推倒重来。滑动窗口的优化思路是既然窗口[i, j]已经满足条件了那么我能不能固定j只把i往右移动直到窗口不满足条件再继续移动j呢这样每个元素最多被访问两次——一次作为右边界进入窗口一次作为左边界离开窗口——总时间复杂度就是O(n)。这个“每个元素最多进出窗口各一次”的直觉就是滑动窗口比暴力解法快一万倍的原因。3. 滑动窗口的核心逻辑左右指针的动态平衡3.1 窗口收缩的触发条件和循环不变量滑动窗口的实现有一个核心的循环不变量在每次循环开始时当前窗口[left, right]是满足“窗口内元素和小于 target”的最大窗口或者理解为在上一次循环结束后窗口刚被收缩到不再满足条件的状态。然后右指针不断扩张一旦发现窗口内的和大于等于 target就尝试收缩左指针并在这个过程中记录最短长度。具体逻辑是这样的初始时left 0right 0当前窗口和为 0右指针right从 0 开始遍历数组每次把nums[right]加入窗口当窗口内元素和s target时记录当前窗口长度right - left 1然后尝试移动左指针left 1并从窗口和中减去nums[left - 1]重复这一步直到s target继续移动右指针。这个逻辑里最关键的点是第三步当窗口满足条件时我们要先记录长度再收缩窗口。有些初学者会把顺序搞反——先收缩再记录这样会漏掉一些合法的子数组。我在草稿纸上推演了几个例子总结出一个很容易记忆的顺序先记录再收缩收缩要收缩到不满足条件为止。3.2 代码实现与每一步的意图def minSubArrayLen(target, nums): n len(nums) left 0 s 0 ans float(inf) for right in range(n): s nums[right] # 右指针扩张把新元素纳入窗口 while s target: ans min(ans, right - left 1) # 先记录当前窗口长度 s - nums[left] # 左指针收缩从窗口和中移除最左边元素 left 1 # 左指针右移 return ans if ans ! float(inf) else 0有一些实现在while循环里会先把s - nums[left]再计算长度这其实是错的——因为移除元素后窗口已经不包含原来的左边界元素了。所以顺序上一定要先计算当前窗口的合法长度再收缩。3.3 为什么每个元素只被访问两次复杂度分析滑动窗口的时间复杂度是O(n)这不是一句空话它的证明很简单right指针从 0 遍历到 n-1一共 n 次left指针最多也只从 0 移动到 n-1一共 n 次。每个元素最多一次进入窗口由right指针完成最多一次离开窗口由left指针完成因此总操作次数不超过2n。空间复杂度是O(1)因为我们只需要两个指针和一个变量记录当前窗口和没有额外的存储结构。这种复杂度分析的方法值得反复体会看一个算法是不是真正达到线性效率不要看循环嵌套的层数而要看数据元素被访问的总次数是否与 n 呈线性关系。滑动窗口里虽然有一个 inner 的while循环但整个算法仍然是线性的因为left指针的总移动次数是有限的。3.4 窗口先后顺序的正确理解一种反直觉的直觉有一个让我自己绕了好一阵的概念滑动窗口的“滑”这个概念很多人理解为“窗口在数组上连续滑动边界一步步挪动”但在实现里右指针不是一步步试探性地移动而是每次循环都果断移动一格再通过while把左指针拉到正确位置。如果你非要用生活化的比喻来理解可以这样想你有一根绳子左边绳头是left右边绳头是right。你不停地从右边拽绳子进来扩张直到绳子上积攒的“重量”窗口和超过目标值这时候你开始从左边收绳子收缩每次收一点就看重量是否还达标一直收到重量刚好低于目标再继续从右边拽。“先拽右边再收左边收紧了再拽右边”这个循环就是滑动窗口的全部精神内核。你写的代码越多越会感觉到这个循环的节奏感——它是一种“呼吸式”的推进方式。4. 换个思路前缀和加二分查找的玩法4.1 前缀和的预处理与等式变形滑动窗口是这道题的主流解法但算法题永远不只有一个解。如果你对“查找”这个操作敏感会发现这道题还可以用二分查找来优化。首先构造前缀和数组pre其中pre[i] nums[0] nums[1] ... nums[i]令pre[-1] 0或者用pre[i]表示前 i 个元素的和即pre[0]0空前缀pre[i]表示前 i 个元素的和。任意子数组[i, j]的和可以表示为sum(i, j) pre[j] - pre[i-1] // 如果用 pre[k] 表示前 k1 个元素的和换一种更顺手的表示令pre[0] 0pre[t] sum(nums[0:t])则子数组[i, j)左闭右开的和是pre[j] - pre[i]。题目要求找到pre[j] - pre[i] target且j - i最小的区间。变形一下pre[j] pre[i] target对于每个固定的i我需要找到一个最小的j使得pre[j]大于等于pre[i] target。由于nums全是正整数前缀和数组pre是严格递增的所以可以在这个递增数组上二分查找满足条件的最小位置。4.2 用bisect_left实现二分查找Python 里实现这个思路非常简洁——用bisect_left直接找到第一个不小于目标值的位置。import bisect def minSubArrayLen(target, nums): n len(nums) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] nums[i - 1] ans float(inf) for i in range(n 1): # 需要找到最小的 j 使得 pre[j] pre[i] target need pre[i] target j bisect.bisect_left(pre, need) if j n: # 区间 [i, j) 的长度是 j - i但 j 必须大于 i if j - i 0: ans min(ans, j - i) return ans if ans ! float(inf) else 0这里有个边界细节值得注意bisect_left返回的j有可能等于i——比如pre[i] target恰好等于pre[i]时即target 0但题目限定 target 是正整数所以不会出现。不过在实际代码中仍需检查j - i 0防止出现长度为 0 的区间。另外bisect_left返回的j如果等于n1说明没有找到满足条件的位置跳过即可。4.3 两种方案的适用场景对比滑动窗口和前綏和加二分都能在O(n)或O(n log n)内解决问题那么什么时候用哪种方案时间复杂度空间复杂度核心优势核心局限滑动窗口O(n)O(1)线性效率空间最优实现简单要求数组元素全为正数和单调前缀和 二分O(n log n)O(n)思路更具一般性后续可扩展到带负数的变体多一个 log n 因子需要额外空间存前缀和实际面试中我认为优先答滑动窗口是稳妥的选择因为它效率更高且代码量少。但如果你能随口说出前缀和加二分的思路并指出两者的适用边界面试官通常会更认可——这体现了你不是只会背模板而是真正理解了单调性这个前提条件。5. 这道题最容易踩的坑边界、初始化与极端用例5.1 不存在满足条件的子数组时返回 0题目明确要求如果不存在符合条件的子数组返回 0。这是最容易被新手忽略的边界条件。我见过不少代码初始化答案时直接把ans设为 0然后在更新时用min(ans, length)——这样会一直得到 0因为min(0, length)永远是 0。正确的做法是把ans初始化为一个不可能更大的值比如float(inf)或者n 1最后再判断是否被更新过。# 错误示范ans 0 会导致 min 永远取 0 # 正确做法初始化为无穷大或 n1还有一种技巧性的写法初始化ans n 1这样如果最终ans仍然是n 1就说明没有找到任何合法子数组返回 0。这种方法不用引入浮点数在整型环境下特别方便。5.2 while 循环和 if 判断的细微差别滑动窗口收缩时用的是while s target而不是if s target。为什么必须循环收缩考虑这样一个场景nums [1, 2, 3, 4, 5]target 7。当右指针移动到 3索引为 3值 4时窗口[0, 3]的和是1234 10 7。此时如果只用if判断一次把左指针右移一位窗口变成[1, 3]和是234 9仍然大于等于 7。而最短的满足条件的子数组其实是[3, 4]和 7长度 2这需要左指针连续右移两次才能达到。所以必须用while循环让左指针一路收缩到窗口刚小于 target 为止并且在收缩过程中不断更新答案。每次收缩都是一个可能更短的合法窗口错过一个都可能错过正确答案。5.3 极端数据与边界用例的测试方法刷算法题时我习惯在写完代码后自己模拟几个极端用例target小于数组中的单个元素比如nums [3, 1, 1]target 2。答案是 1因为nums[0] 3单独就满足条件。所有元素之和刚好等于 target比如nums [1, 2, 3]target 6。答案是 3因为整个数组就是满足条件的唯一子数组不存在更短的。只有一个元素如果该元素大于等于 target答案 1否则返回 0。target极大比如sum(nums) target此时应返回 0窗口在整个过程中永远不会收缩。这些边界用例不仅能帮你验证代码正确性也能帮你在面试中展示严谨性。我一般会单独写一个测试函数循环测试这些用例这比一步步调试更快。6. 从209题出发滑动窗口题型的通用套路6.1 一个可以举一反三的框架模板滑动窗口问题虽然变化多端但其核心框架是高度统一的。做题做多了我总结出一个模板化的写法适用于绝大多数窗口类题目def slidingWindow(nums, k): # 1. 初始化左右指针和窗口状态 left 0 state ... # 窗口内的累计状态可能是和、频率、集合等 ans ... # 2. 主体循环右指针扩张 for right in range(len(nums)): state update(state, nums[right]) # 扩充窗口更新状态 # 3. 条件不满足时左指针收缩 while invalid(state, nums, left): state remove(nums[left]) # 移除左指针元素更新状态 left 1 # 4. 更新答案注意答案可能在收缩前、收缩中、或收缩后更新因题而异 ans update(ans, right - left 1) return ans难点在于第二步和第三步之间的“答案更新时机”——不同题目有不同的更新时机。以 209 题来说答案在收缩过程中更新因为每收缩一次窗口可能仍然满足条件且变得更短。而像“无重复字符的最长子串”答案则在收缩完成后保证窗口无重复更新。吃透这个答案更新时机是滑动窗口从入门到进阶的分水岭。6.2 类似的变式题目与思路迁移209题做熟之后可以顺手刷这几道关联题帮助建立题型认知LeetCode 76 最小覆盖子串给定一个字符串和模式串找到包含模式串所有字符的最短子串。这个题的窗口收缩条件变成了“窗口内字符覆盖模式串的所有字符”需要维护两个哈希表来计数。LeetCode 904 水果成篮这道题把窗口限制改成“最多只能有两种不同元素”收缩条件是“窗口内不同元素种类大于 2”。LeetCode 3 无重复字符的最长子串收缩条件是“窗口内有重复字符”。这些题目乍看各不相同但本质上都是同一套模板右指针不断扩展左指针根据某个条件收缩答案在某个时机更新。209题是理解这套模板的最佳起点因为它没有任何哈希表、字符计数等附加维度纯靠累加和就能驱动窗口滑动。6.3 个人刷题体会和一个小技巧这道题我第一次做的时候用的是暴力解法提交超时然后看题解学到滑动窗口又隔了一周重新自己写结果while循环里顺序写反了先收缩再记录长度导致一个简单的测试用例都过不了。这次失败让我养成一个习惯遇到窗口类题目先在草稿纸上画三五行元素的窗口滑动过程标注清楚“记录长度”的那一步发生在哪一个状态。具体画法是这样把数组写在一条数轴上用方括号标出 left 和 right每次右指针移动一格画一个新状态一旦进入 while 收缩每收缩一格也画一个新状态在检查每个状态时用笔在旁边圈出“此时是否满足条件如果满足当前窗口长度是多少”。这个过程看起来麻烦但对初学者非常有效——它能把代码里的循环逻辑还原成可视化的状态转移一旦代码行为和你的手推过程不一致你就能立刻定位到是收缩顺序出错还是答案更新时机出错。我现在刷题仍然保留这个习惯甚至对一些复杂的双指针题会在白板上画出整个状态序列再写代码。事实证明大多数边界错误都是在画图阶段就能暴露的而不用等到提交之后被测试用例打回。这也算是我从 209 题这道“简单题”身上收获到的最有价值的经验。