滑动窗口算法详解：从双指针到O(n)复杂度的核心原理与实践

1. 从一道“超时”的题说起滑动窗口为什么值得单独写一篇总结先讲个我实际遇到的场景。某次刷题练习时遇到一道求“连续子数组最大和”的题目我按直觉写了双层循环数据规模一上来直接超时。当时旁边一位朋友随口说了句“这题用滑动窗口啊O(n)就完了。”我嘴上没说什么心里其实在想什么窗口怎么滑凭什么能O(n)后来认真啃了几道典型题才意识到滑动窗口不是某个具体的算法库函数而是一种“双指针技巧的进阶形态”。它解决的核心问题绝大多数可以概括成一句话在数组或字符串上维护一个区间让区间满足某种条件然后高效地求与区间相关的某个目标值。这类问题如果暴力求解通常是O(n²)甚至更高而滑动窗口能把复杂度压到O(n)。这篇总结我不想写成一堆题解的堆砌而是想从原理入手把滑动窗口的“为什么能行”讲透再给出一套可以直接套用的思考模板最后用几个经典场景展示怎么落地。不管你是刚开始刷题的新手还是想系统梳理算法的求职者这篇应该都能给你一些可复用的东西。2. 滑动窗口的本质把“重复计算”变成“增量更新”2.1 暴力解法到底慢在哪里先看一个最简单的例子给定一个正整数数组找出和为某个目标值的最短连续子数组长度。暴力思路就是枚举所有起点和终点def min_subarray_len_bruteforce(target, nums): n len(nums) ans float(inf) for i in range(n): for j in range(i, n): s sum(nums[i:j1]) if s target: ans min(ans, j - i 1) break return ans if ans ! float(inf) else 0这个写法的问题在于每换一个起点内层都要重新累加一遍从起点到终点的和。比如数组[1, 2, 3, 4, 5]算[1, 2, 3]的和要加3个数算[1, 2, 3, 4]又要重新加4个数明明[2, 3, 4]和[3, 4, 5]之间有大量重叠元素这些重叠部分被反复扫描了。当数据规模到10万级别这种重复计算基本就宣告不可行了。2.2 窗口的“滑动”究竟滑的是什么滑动窗口的思路很朴素不枚举所有起点和终点而是维护一个“当前区间”通过移动左边界和右边界来更新区间状态。再回到上面那个“正数数组找最短和≥target的子数组”的问题。因为数组元素都是正数所以右边界往右扩展时区间和单调递增这时候一旦满足“区间和≥target”再继续扩展右边界只会让长度更长没有意义。于是我们就收缩左边界看看缩小窗口后是否还能满足条件同时不断记录满足条件时的最小长度。这个过程中右边界每次移动时我只做一件事sum nums[right]左边界每次移动时也只做一件事sum - nums[left]。整个窗口内的数据不需要重新遍历。2.3 窗口三要素左指针、右指针、窗口状态滑动窗口之所以容易写错是因为很多人在代码里没有把“窗口的状态”单独抽象出来。我建议你写任何滑动窗口题之前先想清楚三件事窗口的左右边界怎么定义一般用left和right两个整数表示左闭右开区间[left, right)这样初始化为[0, 0)时窗口为空代码边界更好处理。窗口内需要维护什么状态可能是数字之和、某个字符出现的次数、窗口中不同字符的种类数、窗口内元素的乘积等等。这个状态必须能在左/右边界移动时O(1)更新。什么时候右扩、什么时候左缩这取决于题目要求下面专门展开。明确了这三件事代码结构其实很固定。模板如下def sliding_window_example(nums): n len(nums) left 0 # 根据题目需要维护窗口状态比如 total, counter 等 state ... ans ... for right in range(n): # 1. 把 nums[right] 纳入窗口更新 state # 2. 当窗口需要收缩时移动 left并同步更新 state # 3. 更新答案 ans return ans3. 一个模板走天下两类窗口的收缩时机3.1 类一窗口满足条件后收缩求最短/最小这类题目的典型特征是“求满足某个条件的最短子数组/最小子串”比如上面说的“和≥target的最短子数组”、LeetCode上的“最小覆盖子串”。它们的共性规律是右边界每步扩展一格窗口变长当窗口恰好满足题目要求时尝试收缩左边界收缩后如果仍然满足要求就继续收缩直到不再满足每次收缩前或收缩后记录当前窗口长度取最小值。为什么这种题可以安全地收缩左边界因为当右边界固定在某个位置时窗口长度越短越可能接近“最优解”而继续扩展右边界只会让长度变大。所以一旦窗口满足条件我们就要“榨干”它的潜力在保持满足条件的前提下尽量缩。3.2 类二窗口不满足条件时收缩求最长/最大另一类题目是“求满足条件的最长子数组/最长子串”比如“无重复字符的最长子串”“最多包含K个不同字符的最长子串”。它们的思路正好反过来右边界不断扩展窗口变长每加入一个新元素检查窗口是否还满足条件如果不满足条件就移动左边界直到窗口重新满足条件每次窗口满足条件时更新答案最大长度。这类题收缩左边界不是“有了更好就缩”而是“不缩就违规了”。比如“无重复字符的最长子串”你右边界加入一个重复字符后窗口内出现了重复就必须收缩左边界把那个重复字符挤出窗口否则窗口一直是非法状态。3.3 判断属于哪一类的两个问题清单很多人分不清该用哪类模板我有一个自己常用的判断方式。拿到题先问两个问题题目要求的答案是最短/最小还是最长/最大这个最直接。目标是“最小窗口”时通常是满足条件后收缩目标是“最大窗口”时通常是不满足条件时收缩。窗口扩大时条件是从“不满足”走向“满足”还是从“满足”走向“不满足”比如“和≥target”随着右扩和变大是从不满足走向满足而“窗口内无重复”随着右扩更容易出现重复是从满足走向不满足。前者适合“满足后收缩”后者适合“不满足时收缩”。当然这个判断不是万能的但它能解决刷题中八成以上的滑动窗口题。剩下两成属于非常规题需要结合题目做变形后面统一讲。4. 经典场景拆解从数组到字符串的三种实战理论讲多了容易飘我们落到具体代码上。我选三个最具代表性的场景分别是“和/乘积类”“无重复子串类”“固定窗口类”。每个场景我都会给出代码模板和需要注意的细节。4.1 数组和/乘积类维护一个数值状态先说最基础的“长度最小的子数组”。给定一个正整数数组和目标值target返回和≥target的最短子数组长度。def min_sub_array_len(target, nums): n len(nums) left 0 window_sum 0 ans float(inf) 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 0 if ans float(inf) else ans这里有几个容易踩的细节while而不是if。因为收缩一次后窗口可能仍然满足“和≥target”需要一直缩到不满足为止。更新答案的时机放在收缩循环内部。因为这时候窗口刚刚满足条件而且是在尽可能短的情况下被记录。如果数组里有负数这种模板就不能直接用了。原因很简单加入负数后窗口和不单调右扩不一定让和变大左缩也不一定让和变小模板依赖的单调性没了。负数场景一般要用前缀和加单调队列处理那是另一个话题。乘积类的题也类似比如“乘积小于K的子数组个数”只是把窗口状态从sum换成product收缩的条件从“≥target”变成“≥K”。4.2 字符串无重复子串类用一个 Counter 维护窗口内字符频次第二类经典场景是“求无重复字符的最长子串”。假设输入字符串s我们要找最长的、内部字符全部不重复的子串。from collections import Counter def length_of_longest_substring(s: str) - int: left 0 counter Counter() ans 0 for right, ch in enumerate(s): counter[ch] 1 while counter[ch] 1: counter[s[left]] - 1 left 1 ans max(ans, right - left 1) return ans这个套路的核心在于while counter[s[right]] 1时说明新加入的字符和窗口内已有字符重复了。为了消除重复左指针向右移动同时把移出窗口的字符频次减下去。我实际写代码时曾经犯过一个低级错误只判断新加入的字符频次却忘了在移动左指针时同步更新counter导致left已经越过某些字符但它们的计数还留在counter里。后面的判断就全乱了。所以记住一句话左指针一动状态必须跟着动。4.3 固定窗口类先初始化窗口再整体平移第三类不是“滑着滑着决定收缩”而是窗口长度固定整体平移。典型例子是“大小为K的子数组最大平均数”以及“字符串中所有字母异位词”问题。固定窗口的思路稍有不同先把前K个元素放入窗口处理一次答案然后右边界每前进一位左边界也前进一位窗口像一列火车一样整体移动。def max_average_subarray(nums, k): left 0 window_sum sum(nums[:k]) ans_sum window_sum for right in range(k, len(nums)): window_sum nums[right] - nums[left] left 1 ans_sum max(ans_sum, window_sum) return ans_sum / k这里每次移动只涉及一次加法和一次减法因为窗口宽度不变只是一个元素进来、一个元素出去。注意right和left的同步关系right从k开始而left每次加1两者之差保持为k所以窗口长度恒为k。固定窗口类问题里还有一种变体就是“窗口不一定要连续存在但你只需要统计窗口内某类状态”。比如“找到字符串中所有字母异位词”那种题窗口长度固定为目标字符串长度每次移动都检查窗口内的字符统计是否和目标的字符统计相同。理解成“固定长度频次比较”后代码就很清晰了。5. 什么时候不能用滑动窗口边界条件与两大反例滑动窗口很强但不是万能钥匙。我在实际刷题过程中吃过不少亏整理出两个比较典型的“反例”场景帮助大家在面对新题时先做判断。5.1 反例一状态不具单调性前面反复提到滑动窗口高效的前提是“窗口状态随右扩/左缩具有单调变化趋势”。要么窗口变大时状态单调增加如和值、乘积要么状态单调减少如剩余可用次数否则左右边界的移动就失去了方向性。最典型的反例就是“数组中有负数”的和值问题。窗口状态不是单调的你用更新答案的时机、收缩的时机都会出错。这时候正确的解法往往是前缀和加哈希表、或者前缀和加单调队列优化而不是简单的滑动窗口。另一个容易忽略的例子是“最长且元素互不相同的子数组”里如果出现负数也不会破坏“互不相同”的约束因为重复性判断本身不受数值正负影响。所以不要说“有负数就完全不能用滑动窗口”关键在于窗口维护的状态是否单调。5.2 反例二窗口扩张时状态刷新不能O(1)完成有些题目表面看着像滑动窗口但窗口状态很难在O(1)时间内更新。比如窗口内要维护“中位数”或“最大值”每次移动都涉及排序或重算直接维护就很棘手。最大值那种还相对好办可以用单调队列双端队列来配合窗口实现O(1)取最大值。中位数则需要双堆或“两个有序结构”来维护更新复杂度通常是O(log n)。这种情况下滑动窗口的“窗口”思想仍然存在但已经不能靠一个while循环打天下了需要引入额外的数据结构。我的建议是看到一个题先问“窗口状态是什么”再问“状态更新能不能O(1)”。如果两个答案都很明确恭喜你这题十有八九是标准的滑动窗口题如果状态更新做不到O(1)别硬套模板考虑升级数据结构或者换一种算法思路。6. 滑动窗口的复杂度分析与优化思路6.1 为什么每个元素最多进出窗口各一次理解滑动窗口时间复杂度的关键是搞清楚左右指针各自移动的次数。在一个标准的滑动窗口流程里right从0走到n-1最多移动n次left同样从0开始最远移动到n也最多移动n次。所以两个指针合起来的总移动次数大约是2n每次移动都只做常数级别的状态更新整体时间复杂度就是O(n)。空间复杂度则取决于窗口状态的数据结构如果是简单的sum或product额外空间是O(1)如果窗口里要维护字符频次或元素频次通常是O(字符集大小)或O(k)k是窗口内可能出现的不同元素数。这里有一个直观对比暴力O(n²)和滑动窗口O(n)在数据规模上的差距数据规模 n暴力操作次数约滑动窗口操作次数约1,000500,0002,00010,00050,000,00020,000100,0005,000,000,000200,0001,000,000500,000,000,0002,000,000一旦数据上到十万级别暴力法基本无法在几秒内跑完而滑动窗口几乎是瞬间完成。这也是为什么面试和竞赛里经常出现滑动窗口的原因它用很低的编码复杂度换来了高性能。6.2 从“能用”到“好用”的三点优化滑动窗口模板本身简单但要写得高效、不易错有几个细节值得优化。第一善用while收缩而不是每次都从头计算状态。这一点前面提过但值得再强调很多初学者会把while写成if导致窗口收缩不彻底答案偏大。第二尽可能缩小状态数据结构。比如只需要知道“某个字符出现次数”用Counter完全没问题但如果字符集很小比如只包含小写字母用长度为26的数组[0]*26会更轻量访问速度更快也更容易做对比。我在处理字母异位词类题目时就一直用定长数组省掉了哈希表开链的开销。第三把“扩展右边界”和“收缩左边界”分开写成两个逻辑块。不要在一个循环里既判断收缩条件又处理右边界那样代码会很难读。我见过的很多错误版本都是因为两个逻辑混在一起导致状态更新顺序出错。6.3 一种常见的错误先更新答案还是先收缩很多人写滑动窗口时会纠结“答案更新放在哪一行”。其实判断标准就是你希望答案对应的是哪个状态的窗口。如果题意要求“窗口满足条件时求最短”答案应该放在收缩过程中也就是窗口依然满足条件但长度正在变短的时候如果题意要求“窗口满足条件时求最长”答案应该放在右边界扩展后、窗口还满足条件的时候。这两者不能拍脑袋乱放否则结果大概率不对。我见过一个实际例子有人求“最短覆盖子串”时把答案更新放在了外层循环末尾结果收集到的都是右边界扩展后的窗口长度根本不是最短的覆盖子串。核心原因就是没有明确“答案对应的窗口状态”。7. 实际刷题中的常见坑与排查思路7.1 死循环左指针移动没有更新状态这是滑动窗口代码最常见的运行时错误。表现是程序卡住不动或者超出时间限制。原因一般是left移动了但窗口状态如sum、counter没有同步减少。比如while window_sum target: ans min(ans, right - left 1) left 1 # 忘了 window_sum - nums[left]这时候window_sum一直不减小while条件永远成立left疯狂右移直到越界死循环就出现了。排查方法很简单在while循环内打一个print(left, right, window_sum)看状态是否同步变化。或者你直接记住一条铁律左指针每移动一格必须有一个对应的状态更新语句。7.2 边界错误左闭右开 vs 左闭右闭不同人写滑动窗口时对区间的定义不一样这本身没问题但必须前后一致。我用的是左闭右开[left, right)循环里right从0开始窗口长度是right - left判断数组下标时要注意nums[right]是当前要被纳入窗口的元素。如果你习惯用左闭右闭[left, right]那么初始化right -1会更好否则初始窗口长度为1容易把空窗口的情况搞错。我个人建议初学者统一采用左闭右开因为很多标准库函数和内置函数都使用这个习惯数学上也更不容易出现off-by-one错误。7.3 窗口初始化空窗口还是首元素入窗有些写法会先把nums[0]加入窗口再开始循环有些写法从空窗口开始在循环里逐个加入。两种都可行但我觉得从空窗口开始更统一因为你不用单独处理数组长度为0或1的特殊情况。left 0 state ... for right in range(n): # 先加入 nums[right] # 再判断是否需要收缩这样一个循环解决所有问题逻辑也干净。如果采用“首元素入窗”的写法数组长度检查就必须前置否则容易越界。8. 滑动窗口的变体与进阶单调队列、双指针、哈希表协作8.1 配合单调队列处理“窗口内最大值/最小值”前面提到过如果题目要求窗口内的最大值或最小值那么单纯的滑动窗口状态更新做不到O(1)这时候常见的组合是“滑动窗口 单调队列”。经典场景是“大小为K的滑动窗口最大值”。维护一个双端队列队列里存的是数组下标并且队列中下标对应的元素值保持单调递减。窗口右扩时把队尾所有比当前元素小的下标弹出再把当前下标入队窗口左缩时如果队首的下标已经离开窗口范围就从队首弹出。这样一来队首始终是当前窗口内最大值所在的下标。这种变体仍然保留了“窗口不断左右移动”的框架只是窗口状态的维护从简单数值变成了一个有序结构。理解了基础的滑动窗口再看单调队列就不会觉得突兀。8.2 配合哈希表处理“最多K个不同字符”类问题另一种常见变体是“最多包含K个不同字符的最长子串”。这时候窗口状态需要用哈希表或频次数组记录每个字符在当前窗口中的出现次数同时用一个变量记录当前窗口内不同字符的种类数。收缩时机仍然是“不同字符数超过K”但收缩时不止要左移指针还要同步更新对应字符的频次并且当某个字符频次减到0时记得把“不同字符数”减1。很多初学者会忘了最后这一步导致计数判断出错。所以我把哈希表配合滑动窗口理解为滑动窗口负责区间控制哈希表负责状态量化一旦状态量超标就触发收缩逻辑。8.3 与二分答案组合当“直接滑”不可行时还有一类比较隐蔽的题目比如“求满足某种条件的最长/最短长度”但窗口状态不满足单调性直接滑动会漏解。这时候一种常见策略是“二分答案长度 滑动窗口验证”。具体做法是二分枚举一个窗口长度mid然后用一个固定长度的滑动窗口判断“是否存在长度为mid的窗口满足条件”。如果满足说明答案可能更长继续上调不满足就下调。这类题的关键在于验证某个固定长度是否可行时窗口状态往往又变得有规律了。最典型的是“重复DNA序列”类或“存在某个长度为K的子串满足某性质”类问题。把二分和滑动窗口组合起来会让很多看似不可能滑的题重新变得可行。9. 我自己总结的一套“滑动窗口五步法”最后分享一个我写给自己的固定解题流程。每次遇到疑似滑动窗口的题目我就按这五步走能解决绝大部分问题第一步判题型。题目是否涉及“连续子数组/子串”的某种条件是否求最值或计数如果是先往滑动窗口上想一想。第二步定状态。窗口内需要维护什么信息才能判断条件是数字之和、字符频次、乘积、还是某种计数第三步定收缩时机。窗口满足条件后收缩还是不满足条件时收缩这个判断取决于目标是求最短还是最长以及状态随窗口扩大的走向。第四步写模板。先写右边界扩展的代码再写收缩逻辑最后在正确的位置更新答案。第五步自查边界。数组为空、窗口长度为0、左指针越界、状态更新遗漏每一条都过一遍。这套流程看起来简单但真正做到位并不容易。我见过很多刷题很久的人手里拿着一堆题解却依然在遇到新题时不知道怎么判断“该不该用滑动窗口”。我建议你把上面的五步用在自己的练习里每做一道题都按这五步走一遍形成肌肉记忆。10. 写在最后的一点个人体会滑动窗口算法在数据结构与算法里不算难难的是很多人把它当成一个孤立的技巧去背而不是当成一种思维模型去理解。一旦你把它理解成“双指针 区间状态 增量更新”就会发现它可以扩展出很多变体配合哈希表、配合单调队列、配合二分、甚至在某些离线问题里配合排序都能看到它的影子。我在实际刷题中最深刻的体会是滑动窗口几乎不需要背代码只要想清楚两件事——窗口的状态是什么收缩的时机是什么——代码自然就写出来了。反而是在这两件事上含糊的人才会在细节里反复出bug。如果你正在准备面试或比赛建议先用最简单的“长度最小的子数组”和“无重复字符的最长子串”把两类模板练熟然后再去挑战“最小覆盖子串”“滑动窗口最大值”这些进阶题。等你把这几道题彻底吃透再遇到新的滑动窗口题大概率就能一眼认出它的结构了。