这题我在刷题初期被折磨过很久。明明听说过“滑动窗口”这个名字但真拿到一道“无重复字符的最长子串”还是只会用双层循环暴力解一提交就超时。后来花了一整块时间把“不定长滑动窗口”相关的题目集中过了一遍才算真正搞明白它到底在干嘛为什么两个指针来回挪就能从 O(n²) 变成 O(n)为什么有时候要先收缩再更新答案为什么换一道题又不会写了。这篇文章就围绕“不定长滑动窗口”展开把它的核心机制、代码模板、题型变形和真实面试中容易踩的坑一次讲清楚。适合刚学完基础数据结构、准备系统刷算法题的人也适合那种“滑动窗口看见一道会一道换道题就懵”的选手。1. 从一道高频题说起为什么暴力会超时窗口却能秒解1.1 先看清暴力解法的真实成本以“无重复字符的最长子串”为例题目要求找出一串字符中最长的、内部没有重复字符的连续子串长度。很多人的第一反应是枚举所有子串。一个长度为 n 的字符串连续子串的数量是 n(n1)/2 个再加上每个子串要去重判断总成本就变成了 O(n³)。稍微优化一下比如在枚举起点的时候不断向右扩展并实时判断是否有重复可以压到 O(n²)但面试官看到 O(n²) 依然不满意原因很直接这种解法做了太多重复劳动。比如字符串abcabcbb暴力枚举第一个起点时已经知道abc是非重复的。到了第二个起点b的时候又会重新检查b、bc、bca这些子串里的大部分字符在上一轮里明明已经扫过一遍了。滑动窗口解决的问题就是把这部分重复扫描省掉。1.2 窗口如何做到“只扫一遍”不定长滑动窗口的核心思路并不复杂维护两个指针 left 和 right它们之间夹着的区间就是一个“窗口”。right 负责扩张往里加新元素left 负责收缩把不合法的元素从窗口里赶出去。整个过程像一条蚯蚓右端往前钻左端跟着调整窗口长度时大时小。关键在于right 指针从 0 扫到 n-1只走一轮left 指针虽然也会移动但也是单调往右、最多移动 n 次。这样一来两个指针加起来一共移动 2n 次整个算法的复杂度就是 O(n)空间复杂度取决于窗口内状态存储用的数据结构。很多初学者第一反应是“两个指针移动难道不是嵌套循环吗”其实不是。内层是 while 循环收缩 left但 left 在整个算法里只会增加不会回头所以两个循环的总迭代次数加起来是 2n 这个量级而不是 n²。1.3 什么样的题能让滑动窗口派上用场刷多了之后我总结出三个识别信号同时满足时基本可以优先考虑不定长滑动窗口研究对象是连续子数组或子串而不是任意组合的子序列。题目要求一个关于子数组的最值最长、最短或数量统计。存在一个可以根据问题条件动态收缩的合法状态判断比如字符不能重复、元素和不能超过 k、不同字符数不能超过多少。如果一段代码需要你枚举“所有起点 所有终点”而且终点往后扩的时候起点能否往前进是依赖于当前窗口状态的那不定长滑动窗口基本就是最优解。2. 不定长窗口的核心机制指针怎么动、答案在哪更新、复杂度为什么是 O(n)2.1 一套最常见的长类模板不定长滑动窗口本身没有统一标准写法但大部分“求最长满足条件子串”的题都长得很像。下面这个 Python 模板是我最常用的骨架def solve(s): n len(s) if n 0: return 0 window {} # 记录窗口内元素状态可以是计数、位置等 left 0 ans 0 for right in range(n): # 1. 把 s[right] 加入窗口 c s[right] window[c] window.get(c, 0) 1 # 2. 收缩窗口直到重新满足条件 while not is_valid(window): d s[left] window[d] - 1 if window[d] 0: del window[d] # 也可以不删但要配合其他判断 left 1 # 3. 此时窗口是合法的用当前窗口长度更新答案 ans max(ans, right - left 1) return ans这个模式的骨架是“右扩 - 左缩 - 更新答案”。但你要注意具体到求最短类题目第 3 步的位置要变这一点会在第四章讲透。is_valid(window)是一段需要根据题目写的条件判断。比如无重复字符那就要求窗口里所有字符的计数都等于 1比如字符种类不超过 2 种那就要求len(window) 2比如窗口内所有字符都能被替换成同一个字符那条件就变成了“窗口长度 - 窗口内最大出现次数 可替换次数”。2.2 模板里面的三行关键代码为什么缺一不可第一段“右扩”很好理解每次循环 right 往后移动对应的字符状态必须更新。这个更新有可能是计数加一也有可能记录的是最新位置取决于状态存储结构。第二段“左缩”是整个窗口的灵魂。窗口什么时候开始收缩代表这道题的核心约束是什么。有些同学写的时候喜欢把 while 写成 if这在很多题目里是错的。因为你删掉最左边一个字符后窗口可能还是不合法必须用 while 一直删到重新合法为止。第三段“更新答案”看起来最没技术含量但是位置极容易放错。求最长合法窗口时更新必须发生在收缩完成之后因为收缩完了得到的是“以当前 right 为右端点的最长合法窗口”。如果你在收缩前就更新会把非法窗口的长度也算进去答案就会偏大。2.3 复杂度分析到底怎么跟面试官讲面试时讲复杂度不能只说一句“O(n)”要让对方相信你理解其中的摊销逻辑。right 指针从 0 到 n-1 一共移动 n 次每次移动对应一次外层 for 循环。left 指针虽然会被 while 循环多次移动但 left 本身是单调不减的也就是说整个算法运行期间 left 至多从 0 变成 n永远不会回退所以 left 的移动总次数不超过 n。两个指针的总移动次数是 2n 量级每个指针移动时涉及的状态操作在哈希表或数组上是 O(1)因此总时间复杂度 O(n)。空间复杂度取决于状态里存储的元素数量最坏情况下窗口里包含所有不同元素也就是 O(min(n, 字符集大小))。2.4 模板只是骨架每道题的精髓都在“收缩条件”我见过太多人背模板背得很熟但换一道新题还是不会。原因是他们把注意力全放在模板结构上没有真正去分析“什么时候窗口不合法”。窗口不合法的原因就是题目里最核心的那个限制条件。比如“字符串的排列”要求窗口内的字符出现次数不能超过 p 串里的次数那收缩条件就是某个字符的计数超了或者是窗口长度超过了 p 的长度。比如“替换后的最长重复字符”要求窗口内最多只能有 k 个字符和最大频率字符不一样那收缩条件就是非最大频率字符的数量超过了 k。所以拿到一道新题先别急着写代码先花两分钟回答三个问题窗口里要存什么什么时候窗口变非法收缩到什么时候停下来这三个问题想清楚代码就是模板的照抄。3. 最长类题型窗口收缩是“纠错”重点在合法状态的恢复3.1 经典题无重复字符的最长子串这道题我用上面的模板可以直接套窗口状态存的是字符到计数的映射。def lengthOfLongestSubstring(s: str) - int: n len(s) window {} left 0 ans 0 for right in range(n): ch s[right] window[ch] window.get(ch, 0) 1 while window[ch] 1: # 一旦有重复字符窗口非法 left_ch s[left] window[left_ch] - 1 left 1 ans max(ans, right - left 1) return ans这里收缩条件直接写成window[ch] 1因为重复字符只可能是刚加入的这一个字符导致的。不必遍历整个哈希表去检查是不是所有计数都等于 1这是个小优化但能省掉一些无谓的检查。还有一种更快的优化状态里直接存每个字符最后一次出现的位置left 可以跳跃式前进def lengthOfLongestSubstring(s: str) - int: last {} left 0 ans 0 for right in range(len(s)): ch s[right] if ch in last and last[ch] left: left last[ch] 1 last[ch] right ans max(ans, right - left 1) return ans这个写法的思路是如果当前字符之前出现过而且出现在窗口内那至少要把 left 跳到上次出现位置的后面一位。注意这里last[ch] left的判断不能省否则“之前出现过但已经不在窗口里”的情况也会触发移动 left导致漏答案。3.2 进阶题替换后的最长重复字符这道题比无重复字符难一个档次。题目要求你最多把 k 个字符替换成任意字符使得子串里所有字符都一样求这样的子串最大长度。我能把这个题想明白的关键点在于一个窗口里如果能通过不超过 k 次替换全部变成同一个字符那么其他字符的数量必须不超过 k。也就是说窗口长度 - 窗口内出现次数最多的字符的出现次数 k套进模板里收缩条件就是上述不等式被破坏def characterReplacement(s: str, k: int) - int: count {} left 0 max_count 0 ans 0 for right in range(len(s)): ch s[right] count[ch] count.get(ch, 0) 1 max_count max(max_count, count[ch]) while right - left 1 - max_count k: count[s[left]] - 1 left 1 ans max(ans, right - left 1) return ans这里有个反直觉的点max_count在收缩过程中没有重新计算但它不对流程造成错误影响。原因是当窗口收缩后max_count有可能比实际最大值大偏大的max_count会让不等式更容易满足也就是窗口看起来更合法从而更新出一个偏大的 ans。可一旦 ans 已经因为“虚大”的 max_count 被更新过那这个值对应的窗口在之前某次状态里是真实存在的因此结果仍然成立。这个细节很多资料没讲清楚我第一次看的时候犹豫了很久。不过如果你觉得这个证明绕还有更稳妥的写法收缩后重新遍历 count 找到当前最大值代码多了几行但心理上更踏实。3.3 变形最大连续 1 的个数 III这道题可以看成“替换后的最长重复字符”的二进制版本。数组里只有 0 和 1最多翻转 k 个 0 变成 1求最长的连续 1 子数组。收缩条件就是窗口内 0 的数量不能超过 k。状态存个zero_count就够了不需要哈希表def longestOnes(nums, k): left 0 zero_count 0 ans 0 for right in range(len(nums)): if nums[right] 0: zero_count 1 while zero_count k: if nums[left] 0: zero_count - 1 left 1 ans max(ans, right - left 1) return ans这类题目做多了你会发现最长类题目的代码结构非常统一右指针加状态条件不满足就一直收缩收缩完更新最值。差别只在于状态里的变量是什么、收缩条件是什么。4. 最短类题型窗口收缩是“榨取”重点在极值试探4.1 最短类为什么要把更新答案放在收缩循环里最长类和最短类的模板十分相似但更新答案的位置要调换。看“长度最小的子数组”这道题找出数组中和至少为 target 的长度最小的连续子数组。def minSubArrayLen(target: int, nums: List[int]) - int: left 0 total 0 ans float(inf) for right in range(len(nums)): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return ans if ans ! float(inf) else 0注意这里答案更新放在 while 循环体内每次收缩前都算一次长度。因为我们要找的是最短合法窗口所以一旦窗口合法总和达到 target就要尝试“榨取”左边的空间看能不能在保持合法的前提下把窗口变得更短。每收缩一次都得到一个合法窗口都要拿来更新答案。收缩到 while 条件不满足时窗口已经非法了这时候再更新就没有意义。如果把更新答案移到 while 循环外面那每次 right 移动后只能拿到“当前以 right 结尾的合法最短窗口”的长度而最短答案可能出现在 right 移动过程中多次收缩的中间状态这样就会漏答案。4.2 进阶题最小覆盖子串这道题是面试常客。题目给一个字符串 s 和一个模式串 t要求在 s 中找到包含 t 全部字符的最短连续子串。状态存储用两个字典一个是 t 的需求字典一个是窗口内的实际计数。收缩条件就是当前窗口已经“覆盖”了 t。def minWindow(s: str, t: str) - str: from collections import Counter need Counter(t) remain len(t) # 还需要匹配的字符总数 left 0 ans_start 0 ans_len float(inf) for right in range(len(s)): ch s[right] if ch in need: if need[ch] 0: remain - 1 need[ch] - 1 while remain 0: if right - left 1 ans_len: ans_len right - left 1 ans_start left left_ch s[left] if left_ch in need: need[left_ch] 1 if need[left_ch] 0: remain 1 left 1 return s[ans_start:ans_start ans_len] if ans_len ! float(inf) else 这里用一个remain变量来判断覆盖状态比每次比较两个 Counter 要高效得多。核心思想是need字典里的值可能为负数表示窗口里某个字符超出了需求量只有need[ch] 0的时候才说明这个字符真的还没有匹配够。我一开始很不适应need字典被改得面目全非这个写法总觉得原来的需求会被破坏。但其实这是一种“额度”思想把 t 的需求量当作初始额度窗口每吃进一个字符就消耗额度每吐出一个字符就恢复额度。窗口需要做的就是把额度消耗到“非正”也就是每个字符都至少满足了。4.3 最短类题目的共性特征最短类题目通常有这些标志词最短、最少、至少、覆盖、都包含。收缩驱动条件是“窗口满足了某个完整需求”比如和至少达到 target、包含所有目标字符、窗口内至少出现 k 次某元素。这类题还有个常见盲区初始化 ans 要用一个极大值不能和最长类一样用 0。最后判断是否有答案的时候也要单独处理否则输出空串或者 0 的时候容易出错。5. 变形题与经典实战字符串排列、滑动窗口最大值和不定长思想的边界5.1 字符串排列定长窗口也可以和哈希表计数结合题目“字符串的排列”要求判断 s2 中是否存在一个子串是 s1 的排列。排列意味着字符种类和数量完全一致只是顺序不同。所以本质上就是找一个长度固定为 len(s1) 的窗口字符计数和 s1 相同。虽然这题看起来是定长窗口但很多人的思路会自然走回不定长的哈希表统计。此时可以直接把窗口长度固定住每次右移一位同时左移一位保证窗口长度不变def checkInclusion(s1: str, s2: str) - bool: if len(s1) len(s2): return False need [0] * 26 for ch in s1: need[ord(ch) - ord(a)] 1 window [0] * 26 n1 len(s1) for right in range(len(s2)): window[ord(s2[right]) - ord(a)] 1 if right n1: window[ord(s2[right - n1]) - ord(a)] - 1 if window need: return True return False这是定长窗口和哈希表计数结合的思路。但如果你用不定长模板去做这题也可以先右扩检测到某个字符计数超过了 need 中的额度就收缩直到计数重新符合要求同时检测窗口长度是否刚好等于 n1。两种写法都能过但你得理解它们之间的转换关系才不会在考场上写着写着混掉。5.2 滑动窗口最大值窗口内不止要维护计数还要维护单调队列“滑动窗口最大值”是另一种形式的窗口题窗口长度固定为 k要求快速获得每个窗口的最大值。很多人在这一步会感到窗口的思想不够用了因为计数解决不了“最大值”这个问题。这时候需要引入单调双向队列。队列里保存的是元素的下标同时保证这些下标对应的数组元素值在队列中单调递减。窗口每次移动时先把队首超出窗口左边界的老元素移除然后从队尾开始把所有比新元素小的元素全部弹出再把新元素下标放入队尾。这样队首永远是当前窗口的最大值。from collections import deque def maxSlidingWindow(nums, k): dq deque() ans [] for right in range(len(nums)): # 移除窗口外的元素 if dq and dq[0] right - k: dq.popleft() # 维护单调递减 while dq and nums[dq[-1]] nums[right]: dq.pop() dq.append(right) # 窗口形成后才能取最大值 if right k - 1: ans.append(nums[dq[0]]) return ans这道题的意义在于告诉你窗口本身只是一种区间维护的思想不局限于“计数 收缩”这一套组合。窗口内需要什么信息就用对应的高效结构去维护。不定长滑动窗口解决的是变长区间的最值问题而维护最大值这种更局部的问题需要引入单调队列。这两个东西经常被放在一起讲但要分清它们的适用范围。5.3 不定长思想在双指针家族中的位置不定长滑动窗口本质上是一种特殊的双指针但不要把它和每一道双指针题都画等号。双指针的范围更广比如链表里的快慢指针、有序数组里的对撞指针它们的移动动机和窗口并不一样。滑动窗口的特点是left 和 right 指向的区间是一个连续的“窗口”窗口里的内容需要被整体维护。因此判断一道题要用滑动窗口关键词一定要落在“连续子数组、连续子串”上面。如果题目不存在连续性要求比如让你从数组中选任意几个数凑一个目标值那滑动窗口就不适用应该往背包、哈希表或者其它方向想。我在面试中就犯过这个错误遇到一道“和为 target 的最短元素组合”第一反应写了个滑动窗口跑样例才发现题目完全没说元素连续。后来长了记性看到 “subarray” 才往窗口上想看到 “subset” 就立刻切到其它思路。6. 边界条件、调试技巧与高频失分点6.1 空输入和初始值最不起眼也最致命很多人在力扣上提交错误不是因为思路不对而是空数组、空字符串这种边界没处理。最长类题目输入空串循环直接不执行返回 ans 初始值。如果初始值设成 0问题不大。最短类题目输入空数组ans 初始值要设成极大值最后要判断有没有合法答案。如果最后直接返回ans可能输出的是无穷大或一个奇怪的数。数组长度为 1 的测试用例也要在思考范围内走一遍检查 left 和 right 会不会越界窗口是否正常更新。6.2 收缩的时候left 到底最多能走到哪left 的边界是一个经常被忽略的问题。理论上 left 最大能到 right 1此时窗口为空。大部分情况下窗口为空时状态自然恢复初始值不会出错。但如果你在 while 循环里用了类似s[left]的访问而且 left 已经越过了 right在某些边界条件下就可能发生 index out of range。稳妥的做法是在收缩循环里确保left right这个前提。如果收缩条件本身是“窗口非法”且非法状态一般不会在窗口为空时成立那 left 就不会超过 right 1但写代码时还是要心里有数。6.3 哈希表和数组的选择不要迷信任何一种窗口内状态存储有两种主流方式哈希表字典和定长数组。在字符类问题上如果字符集是有限的比如 26 个小写字母用长度为 26 的数组最省心。比较两个数组是否相等可以直接window need时间复杂度 O(26)常数很小。如果字符集很大或者元素类型是字符串、对象哈希表更合适。有些同学习惯把所有题都写成哈希表这没毛病但注意用字典时删除计数为 0 的键值要小心。删除的好处是 len(window) 能准确反映窗口内不同字符的数量不删除的好处是代码简单少写两行。两种方式取决于你后面的判断条件用不用 len(window)。6.4 调试窗口题的三个实用招数窗口题调试起来比别的算法更难因为状态是动态的肉眼很难追踪。我自己的经验是第一打印每轮循环的窗口区间和状态变量。比如在代码里加一行print(left, right, window)。这样能直观看到窗口的收缩是否按预期发生。第二构造一个最短的失败用例手动推演。比如最小覆盖子串这道题拿s ADOBECODEBANC, t ABC手动模拟两三轮基本能找到逻辑漏洞。第三边界用例要单独跑比如s a, t aa、s , t a这种极端输入。6.5 窗口题的面试表达顺序面试时被考到窗口题不要上来就写代码。我先说三句话这道题研究对象是连续子数组可以用滑动窗口窗口里需要维护什么状态什么条件下窗口需要收缩收缩完之后如何更新答案。面试官听完这三句话基本就能判断你是不是真懂。比直接默写模板要加分得多。最后分享一点我的实际经验刷不定长滑动窗口的题最忌讳的就是只背模板。我在最开始的一个月里靠模板能做出见过的题但一到变体题就卡住。后来我强迫自己每做一道题都在笔记本上写三行窗口存的是什么收缩条件是什么为什么答案更新在这个位置。写了几十道之后突然有一天就觉得这类题“通了”。建议你按这个顺序刷题先从无重复字符最长子串入手然后做长度最小的子数组体会最长和最短两类答案更新位置的差异之后刷字符串排列、替换后的最长重复字符这两个变体掌握哈希表和数组两种状态存储方式最后用最小覆盖子串和滑动窗口最大值各练一题感受窗口思想和单调队列的结合。这个顺序基本覆盖了不定长滑动窗口的高频考法刷完再遇到相似题就只剩角度转换的问题了。