刷过一阵子算法题的人多少都有感觉滑动窗口这四个字几乎每个热门题单里都会出现。而长度最小的子数组这道题往往就是很多人第一次和滑动窗口正面交手的地方。它看起来并不吓人——不就是找一段连续数字让它们的和超过某个给定值吗可真到了面试现场能一次写对的人并不多。这篇文章就聚焦这一道题给你一个正整数数组nums和一个目标值target找出满足“元素之和大于等于target”的长度最小的连续子数组返回它的长度如果压根不存在返回 0。我会从暴力解法为什么不行讲起把滑动窗口的每一步推演、参考代码、边界情况和常见坑都过一遍最后还会聊聊和它同名的“滑动窗口最大值”“滑动平均滤波”等概念之间的区别。适合刚接触双指针的初学者也适合准备面试时想把这一套逻辑彻底理清的人。1. 先把这个题吃透原题、数据范围和直觉陷阱1.1 原题到底在问什么这个题的原型非常经典LeetCode 编号 209。描述可以总结成一句话给定一个含有n个正整数的数组nums和一个正整数target找出数组中满足其元素和大于等于target的长度最小的连续子数组返回其长度。如果不存在返回 0。比如下面这个例子target 7nums [2,3,1,2,4,3]所有满足和大于等于 7 的连续子数组里最短的是[4,3]长度为 2所以答案是 2。再看两个典型边界target 4nums [1,4,4]答案是 1因为单个元素4已经满足条件。target 11nums [1,1,1,1,1,1,1,1]所有元素加起来才 8没有任何子数组满足条件返回 0。数据范围一般到10^5量级target最大可以去到10^9nums[i]最大10^4。这个范围设计是有意的它逼着你放弃O(n^2)的暴力枚举转而考虑线性或接近线性的解法。1.2 为什么暴力解法在真实数据面前必挂很多人的第一反应是枚举。外层循环固定子数组的起点内层循环往后扩展终点每得到一个区间就算一次和维护一个最小长度。这种做法思路完全正确但代价太高。假设数组长度n 10^5简单枚举所有起点和终点区间个数大约是n * (n 1) / 2也就是大约5 * 10^9个。即使每个区间只用极短时间处理这个数量级在普通面试环境里也是不可能跑完的。哪怕你提前用前缀和把“求任意区间和”优化成O(1)整体仍然停留在O(n^2)依然是10^10次级别操作放在限时判题环境里基本超时。所以这道题的核心难点不是“知不知道要枚举”而是“如何用更聪明的方式减少无效枚举”。滑动窗口之所以能派上用场靠的就是把起点和终点都设计成“只前进、不后退”的指针从而把一个可能O(n^2)的搜索过程压缩到O(n)。1.3 什么时候该想到用滑动窗口什么时候不能硬套滑动窗口不是万能的。它比较适合解决“连续区间 区间状态可以由一个变量快速维护”这类问题。展开来说一个结构适合用滑动窗口通常满足几个特征研究对象是数组或字符串里的连续一段随着窗口变大某个状态量呈单调趋势比如这里窗口和只会越加越大窗口左端收缩时可以通过已经维护的变量快速更新状态不需要重新扫描窗口内元素这道题完美命中这些条件数组是正整数所以窗口向右扩张时总和只增不减当总和超过target后为了找更短区间左指针右移总和又只减不增。这种“单调增减”让双指针可以放心移动。但如果你遇到的是带负数的数组或者要求找“和恰好等于 target”的区间情况就不一样了。带负数时窗口扩张不一定让总和变大左指针移动也不一定让总和变小双指针的单调性假设被打破滑动窗口就不能硬套。这时候往往需要前缀和加哈希表或者其他专门解法。2. 滑动窗口的运行原理右指针加水左指针放水2.1 窗口的状态维护策略滑动窗口的代码写起来很短但背后是一套非常明确的状态维护策略。你可以把它想象成一根水管右指针right负责“加水”每轮把nums[right]加进当前窗口和左指针left负责“放水”当窗口内的和已经大于等于目标值时试着从左边移除一个元素看窗口能不能更短窗口内始终维护一个“当前连续子数组的和”整个过程中我们追求的不是“窗口一直满足条件”而是“窗口要么刚好满足条件要么差一点就能满足”。换句话说维护的是一种近似临界的状态。当和已经达到target时立刻记录当前长度然后收缩左端收缩到不满足条件为止再去扩展右端。这样每一轮循环都会得到一组候选答案最终取最小。用大白话讲就是右指针尽量多捞水捞到够用了就记一下当前桶的长度然后从左端倒掉一点水看看还能不能更短。倒到不够用了右指针继续往前捞。2.2 手推一遍示例target7, nums[2,3,1,2,4,3]光讲概念不够我们完整走一遍target 7、nums [2,3,1,2,4,3]的过程。初始化left 0window_sum 0ans n 1 7。右指针加水后的窗口和收缩前的情况收缩过程本轮后的答案022 7不收缩无7155 7不收缩无7266 7不收缩无738窗口[2,3,1,2]长度为 4满足条件减去nums[0]2窗口和变 6left14410窗口[3,1,2,4]长度为 4满足条件减 3 得 7left2仍满足记长度 3再减 1 得 6left3359窗口[2,4,3]长度为 3满足条件减 2 得 7left4仍满足记长度 2再减 4 得 3left52注意第 4 行和第 5 行收缩过程可以连续发生多次直到窗口和小于target为止。最终答案取到 2对应子数组[4,3]和题目预期一致。这里有一个很容易忽略的细节更新答案的时机必须放在“窗口和满足条件”这个判断之内。也就是说先判断window_sum target再执行ans min(ans, right - left 1)然后才收缩左端。很多人写错是因为把答案更新放在了 while 循环外面结果把不满足条件的窗口长度也算进去或者漏掉了收缩过程中出现的更短窗口。2.3 复杂度为什么是 O(n)元素的进出次数是关键表面上看外层right要移动n次内层while还可能连续收缩似乎复杂度不是严格的O(n)。但仔细一想就会发现right指针从 0 走到n-1总共只前进n次left指针虽然可能在某个right轮次里连续移动多次但它整体只会向右移动最多从 0 移动到n也就是最多n次因此每个元素“进入窗口”一次“离开窗口”最多一次。整个算法的时间复杂度就是O(2n)去掉常数后是O(n)。空间上只维护了几个变量所以是O(1)。这种分析方式叫摊还分析在滑动窗口类题目里非常常见。面试时讲完代码如果能补一句“每个元素最多被 left 和 right 各访问一次所以总操作次数不超过 2n”会显得你对复杂度理解得很扎实。3. 代码落地标准实现与两个容易翻车的细节3.1 双指针版本最稳的写法与逐行注释以 Python 为例最稳妥的滑动窗口写法如下def min_subarray_len(target: int, nums: list[int]) - int: n len(nums) left 0 window_sum 0 ans n 1 # 用一个超过最大可能长度的值作为“找不到”标记 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 # 如果 ans 仍然是初始值说明没有找到合法子数组 return ans if ans ! n 1 else 0几个关键位置值得反复确认先加右指针的值再进入 while。顺序不能反否则第一轮就会漏掉当前元素。答案更新写在 while 内部。因为只要进入 while窗口就是合法的此时记录长度不会出错。收缩时先减去nums[left]再让left 1。如果顺序写成先移动 left 再减减掉的就会是错误位置的值。ans初始化为n 1而不是 0。如果初始化成 0后面min会把所有候选答案都压成 0最终返回 0但这里的 0 会被误判成“不存在”。如果你用的是 C 或 Java写法逻辑完全一样只需把语言层面的类型注意一下。window_sum在极端情况下可能接近10^5 * 10^4 10^9用int还够但如果你对题目做扩展比如数组更长或者元素值更大最好直接开long类型免得溢出。3.2 另一个思路前缀和 二分查找除了双指针这道题还有一个值得一提的替代解法先把前缀和数组算出来再对每个位置做二分查找。因为所有元素都是正整数前缀和数组prefix是严格递增的。有了这个单调性我们就可以二分。对于每个右端点i要找的是满足prefix[i] - prefix[j] target的最大j也就是prefix[j] prefix[i] - target由于我们要的是“以 i 结尾的最短区间”所以j越靠右区间越短。用bisect_right找到“最后一个小于等于目标值的位置”就能直接算出候选长度。import bisect def min_subarray_len_with_prefix(target: int, nums: list[int]) - int: n len(nums) if n 0: return 0 prefix [0] * (n 1) for i, num in enumerate(nums): prefix[i 1] prefix[i] num ans n 1 for i in range(1, n 1): # 在 prefix[0:i] 中找最后一个 prefix[i] - target 的位置 j bisect.bisect_right(prefix, prefix[i] - target, 0, i) - 1 if j 0: ans min(ans, i - j) return ans if ans ! n 1 else 0这里二分查找的右边界必须写成i因为窗口至少包含nums[i-1]左边界最多到i-1也就是prefix下标最多到i-1。把i排除在搜索范围外才不会出现“空窗口”被当成合法候选的尴尬。这个解法的复杂度是O(n log n)空间O(n)。在n 10^5的场景下也能通过只是比双指针慢一些代码也稍微绕一点。3.3 两种方案的取舍我把两种方案放在一起比较一下方案时间复杂度空间复杂度写起来优点滑动窗口双指针O(n)O(1)简单直接代码短效率高面试首选前缀和 二分O(n log n)O(n)需要理解二分边界能顺便复习前缀和与二分另类加分项实际面试或者做题时我的建议是先流畅地写出滑动窗口版本然后如果时间允许再主动提一句“如果换一种思路也可以先维护前缀和再利用单调性做二分查找”。这既能展示你掌握双指针又表明你理解为什么这个解法成立——前缀和的单调性来自正整数约束。需要再啰嗦一句前缀和 二分依赖“前缀和递增”这个前提一旦数组里出现负数这个前提就没了二分会失效。而双指针如果直接套到负数场景同样可能出错因为窗口和不再随右指针扩张而单调增加。题目里明确说了nums[i]是正整数所以两个方案都能用。4. 边界条件、常见误区和一套自检清单4.1 不存在答案时的返回值原题有一个让人容易忽略的返回值设计如果所有元素加起来都不够target返回 0而不是返回n也不是返回某个特殊长度。上面代码里ans初始化为n 1这个值天然大于任何真实窗口长度。如果整个循环结束后ans还是n 1说明搜索过程中没有任何一次window_sum target也就是不存在合法子数组。此时返回 0。一个常见的低级错误是最后直接return ans然后发现所有元素和不够target时返回了一个n1这个奇怪数字。另一个错误是初始化ans 0然后min(0, 合法长度)永远输出 0。这两个坑都源于对哨兵值理解不透。4.2 等于 target 和大于 target 必须一起处理while循环的判断条件是window_sum target这里要特别留意而不是。有的同学觉得“大于等于”和“大于”只差一个等号影响不大。但实际上如果数组里恰好存在一个子数组的和正好等于target用会直接跳过它。比如target 4nums [1,4,4]正确答案是 1因为第二个元素本身就是 4。如果条件写成window_sum target这个长度为 1 的合法窗口永远不会被记录最终答案会变成 2直接判错。从另一个角度看题目求的是“大于等于 target”等于的情况当然也是合法候选所以判断条件必须是。4.3 空数组、单元素和整数溢出虽然原题一般保证数组非空但工程习惯好的代码还是会在开头加一句防御if not nums: return 0这样即使换一套测试数据也不会崩。单元素数组的情况也要想清楚如果nums[0] target答案是 1否则因为只有一个元素不可能有其他组合答案就是 0。这套逻辑放进双指针代码里其实完全自洽不需要额外写分支但自己在心里过一遍总没坏处。整数溢出是 C/Java 用户需要额外注意的。一个n 10^5、每个元素10^4的数组窗口和最高能到10^9int还勉强装得下可一旦题目扩大规模或者你顺手改造成“总和非负但更大”的版本window_sum就可能爆。如果写前缀和版本prefix数组同样面临这个问题。Python 没有这个烦恼但用其他语言时建议直接用long避免在极端数据上翻车。还有一个细节值得讲当某个元素本身已经大于等于target时while循环会把left一直移动到right 1也就是说left会短暂地超过right。这不会造成问题因为答案更新只发生在 while 开头那时的窗口一定还有元素。收缩到window_sum 0后退出循环下一轮right继续前进窗口重新开始积累。4.4 自检清单我自己每写完一版滑动窗口代码会对着这套清单快速过一遍右指针是否每轮都先加值再加进window_sumwhile 条件是不是 target答案更新是不是在 while 内部收缩时是不是先减nums[left]再移动leftans的初始值是否足以区分“有答案”和“无答案”最后返回时能不能正确处理“所有元素和都小于 target”的情况数组为空、只有一个元素等极端输入代码是否自然成立这套清单不仅适用于这道题后面刷其他双指针题目时也基本通用。5. 名字相同但思路不同的滑动窗口单调队列与工程类比5.1 滑动窗口最大值为什么普通双指针解决不了聊完“长度最小的子数组”很多人会产生一个疑问同样是滑动窗口为什么另一道经典题“滑动窗口最大值”就不能用两个指针加一个和变量解决原因在于这道题需要维护的信息是“窗口内的最大值”。当你把左指针往右移时如果移出去的元素恰好是当前最大值你没法仅凭一个变量知道新的最大值是谁。你必须在窗口里重新扫描才能确定新最大值这样一来最坏情况下时间复杂度就退化成了O(nk)。相比之下“长度最小的子数组”维护的是窗口内所有元素的和。左指针移出元素时只需要做一次减法就能得到新窗口和这个操作是O(1)。所以两个题目虽然都叫滑动窗口需要的数据结构却完全不同一个只需要普通双指针另一个需要单调队列。5.2 单调队列的维护口诀和参考代码“滑动窗口最大值”的正解是维护一个双端队列队列里存的是数组下标而不是元素值本身。维护的口诀可以总结成三句话队伍头部是当前窗口最大值的下标每次右指针前进先判断队头下标是否已经离开窗口离开就弹出新元素入队前把队尾所有“值小于等于新元素”的下标全部弹出因为它们又老又不够大不可能再当最大值这个“又老又不够大”的淘汰逻辑是单调队列的精髓。用代码表达如下from collections import deque def max_sliding_window(nums: list[int], k: int) - list[int]: q deque() ans [] for i, x in enumerate(nums): # 队头元素如果已经不在窗口内弹出 while q and q[0] i - k: q.popleft() # 新元素比队尾元素更大队尾元素永远不可能成为最大值 while q and nums[q[-1]] x: q.pop() q.append(i) # 窗口形成后队头就是当前窗口最大值 if i k - 1: ans.append(nums[q[0]]) return ans如果你没接触过这个套路第一次看可能会觉得奇怪为什么新元素可以把队尾比它小的元素弹掉因为数组下标只会越来越大那个被弹掉的旧元素已经既没有值优势也没有新鲜度优势了留着它纯属浪费空间。每个元素同样至多入队一次、出队一次所以总复杂度也是O(n)。5.3 滑动窗口在工程里的两个常见身影平滑滤波与传输窗口“滑动窗口”这一概念并不只活在算法题里。工程领域里有两个很常见的身影和它名字相同但含义稍有不同。第一个是滑动窗口滤波也叫滑动平均滤波。很多传感器数据会有高频噪声嵌入式里最简单的处理办法就是维护最近N个采样值的平均值。每来一个新样本就丢一个最老样本平均值随之更新。这和“长度最小的子数组”其实神似都是在连续数据流上维护一个固定窗口区别是算法题要动态伸缩窗口滤波则往往用固定窗口。滑动平均有一个很实际的问题叫滤波器延迟。因为输出是窗口内样本的平均当信号真实变化时平均值会有滞后。窗口越长平滑效果越好但延迟也越大大约是(N-1)/2个采样周期。这就需要在“平滑”和“实时性”之间做取舍新手容易忽略。第二个身影是网络传输里的滑动窗口机制。发送端维持一个窗口窗口内可以连续发送多个数据单元收到确认后再把窗口往前移动。这和算法题的窗口很不一样前者把窗口大小当作“并发在途数量”后者聚焦“连续子数组的区间覆盖”但“窗口滑动”这个直觉是一致的窗口不是一次性铺满整条数据流而是始终保留最近一段需要关注的数据。这也是我为什么建议初学者一定要亲手把“长度最小的子数组”的每一步窗口变化画出来。把窗口从“抽象概念”变成“可视化的区间”之后再看 TCP 窗口、滑动平均滤波甚至日志系统里的时间窗口统计都会觉得到处是同一个套路。6. 刷完这道题之后下一步练什么6.1 同一套思路的变体题单“长度最小的子数组”是滑动窗口入门第一题但它只是起点。想真正把滑动窗口练熟我建议按下面这个顺序往下刷无重复字符的最长子串窗口内维护的不是和而是一个字符集合需要配合哈希表或数组记录出现次数水果成篮窗口内维护的是“最多两种不同元素”这个条件重点练收缩逻辑最大连续 1 的个数 III允许把最多 K 个 0 翻转成 1窗口内要数 0 的个数等于给窗口加了一个额外限制最小覆盖子串窗口从“数值和”升级成“字符频次达标”需要维护一个计数状态滑动窗口最大值刚才说的单调队列题练的是“窗口内的动态极值”数据结构升级为双端队列字符串的排列判断输入的字符串是否包含某个排列本质是固定长度窗口的字符频次比较这些题共用同一个内核但每道题的窗口状态定义都不一样。你刷完第一遍后会发现一个特别重要的模式滑动窗口题的核心永远是“右指针加元素、左指针删元素、中间维护一个可快速更新的状态量”。想清楚状态量是什么代码基本就出来了。6.2 我的个人刷题体会这道题我刷过很多遍每次给新人讲完感触最深的一点是滑动窗口的代码太短短到容易让人以为它不重要。但它背后那种“两个指针不回头”的思维才是算法里非常核心的东西。面试时我通常会这么做先快速写出双指针解法然后边写边讲解“右指针负责扩张左指针负责收缩”最后再专门用两句话解释为什么复杂度是 O(n)。这个表达顺序比直接甩出代码效果好得多。如果非要说一条避坑经验那就是一定要亲手在纸上推一遍那个[2,3,1,2,4,3]的例子尤其是最后两步收缩过程。推完之后你就会发现所谓“窗口滑动”并不是一个抽象的概念而是一组非常具体的左右指针移动规则。之后你再去看单调队列、滑动平均滤波、传输窗口这些名词都会觉得它们背后共用同一个直觉用最近一段连续数据的统计信息代替对全量数据的反复扫描。