做算法题的人第一次接触“滑动窗口”这四个字多半是在“长度最小的子数组”那道题上。“窗口”这个词很形象数组就像一条长街窗口就是你的视线范围。固定窗口是视线宽度恒定无论前面出现什么你都只能看这么多而不定长滑动窗口则是视线范围随条件伸缩——看到目标就收紧没看到就放开。今天这篇基础篇想把不定长滑动窗口一次讲透它和固定窗口到底有什么区别、核心模板怎么背、三个最经典的题目如何从暴力一步步优化过来以及我刷题时踩过的一堆坑。适合刚接触滑动窗口的读者也适合那些自认为会一点、但每次写出来总差一点的人。这个标题叫“不定长”其实对应的是算法题里非常大的一类问题不是告诉你窗口长度k而是让你找一个连续区间满足某个约束条件然后求最长、最短或数量。这种问题如果不用滑动窗口暴力解法通常直接爆炸。所以把这套基础打牢后面遇到“最多k个不同字符”“包含至少k个重复字符”“最小覆盖子串”这些变体时你会比别人轻松很多。1. 先搞明白不定长滑动窗口和固定窗口根本不是一回事1.1 固定窗口一个大小不变的框固定窗口很好理解。比如信号处理里的滑动窗口滤波取一个长度为N的窗在信号序列上每移动一位计算窗内数据的平均值或中值。窗口尺寸从头到尾不变N是多少就是多少。算法题里对应的就是“长度为k的子数组最大和”“滑动窗口最大值”“滑动窗口中位数”这类题它们都有一个明确的k窗口每次移动只淘汰一个旧元素、加入一个新元素维护成本很低。固定窗口的核心特征是长度已知且恒定。你不需要思考窗口什么时候该扩大、什么时候该缩小只需要维护好滑动的过程。所以这类题的难点通常不在窗口本身的调整而在于“如何在窗口变化时快速拿到极值或统计量”这才会用到单调队列、对顶堆、哈希计数之类的工具。1.2 不定长窗口两个边界都在动的合法区间不定长滑动窗口也叫可变窗口、双指针维护区间。窗口用[left, right]表示left和right都从数组起点出发right负责不断向右扩展left负责在条件不满足时向右收缩。窗口长度right-left1是动态变化的完全由当前数据决定。我习惯用一个买菜的例子来理解它你有一个篮子不停往里面放苹果直到总重量超过预算。一旦超预算你就要从最早放进去的苹果开始往外拿直到篮子重新变轻。每一次“超预算后刚刚恢复”的篮子大小都是当前右边界下的一个候选答案。这个篮子的容量从来不是固定的它由“总重量不超过预算”这个条件决定。不定长滑动窗口解决的就是一类通用问题在所有连续子数组中找到满足某个约束条件的最优区间。约束条件可能是“和大于等于target”可能是“没有重复字符”也可能是“覆盖字符串t的所有字符”。窗口是否合法用一个状态来衡量right扩展改变状态left收缩恢复状态。1.3 为什么它能把O(n²)变成O(n)单调性前提这里要着重讲一个关键前提因为很多新手一上来就套模板遇到负数数组直接翻车。不定长滑动窗口能高效工作的前提是窗口的“合法判断”必须具备单调性。什么意思固定left不动right越往右窗口只会越来越大于是窗口内某个衡量状态的量会朝一个固定方向变化。比如数组全为正数时窗口和随着right增加单调递增一旦超过target继续右扩只会更超不会自己恢复。窗口内字符重复次数随着right增加单调不减一旦出现重复继续右扩不会自动消重。覆盖缺口数在加入字符时只可能减少或维持不会无端增加。因为状态单调变化所以当窗口非法时继续右扩没有任何意义唯一正确的操作就是收缩left等待下一次扩展。而left每次收缩也只是把状态向“更容易合法”的方向推每个元素最多被left移出一次、被right加入一次总操作次数O(2n)均摊下来就是O(n)。如果数组里有负数子数组和随right增大可能先升后降不再单调滑动窗口的“非法后只能收缩”的推理就失效了必须另找思路。这一点到第5章还会再提。2. 一套模板打天下核心代码骨架与答案更新位置2.1 模板代码右边界扩张、左边界收缩、状态维护不定长滑动窗口的代码长得非常像我可以给一个抽象模板后面三个经典题全是从它变形来的def slide(nums): n len(nums) left 0 state init_state() # 初始状态例如和为0、频次数组全0 ans ... # 根据题目设置初始答案 for right in range(n): state add(state, nums[right]) # 1. 右边界扩展更新状态 while not valid(state) and left right: # 2. 窗口非法收缩左边界 state remove(state, nums[left]) # 3. 移除时同步更新状态 left 1 # 4. 此时窗口合法根据题型更新答案 ans update(ans, right - left 1) return ans这套模板真正的精华不是那几行循环而是你如何定义add、remove、valid三个操作。不同的题状态结构完全不同长度最小的子数组状态就是当前窗口的total_sum无重复字符的最长子串状态是一张频次表cnt最小覆盖子串状态是窗口频次win、目标频次need以及一个matched计数。模板的价值在于帮你固定流程先加后收、收了再更新。只要这个顺序不乱具体题目的适配就只是改状态。2.2 答案到底在哪里更新三种情况必须分清模板里第4步注释写的是“此时窗口合法根据题型更新答案”但实际操作中答案的更新位置有三种这是新手最容易搞混的地方。第一种求最长合法窗口长度。典型如无重复字符的最长子串。你应该把窗口收缩到完全合法之后再用ans max(ans, right - left 1)更新答案。因为只有收缩完成后窗口才是合法的此时的长度才是以right结尾的最长合法窗口。如果你在收缩前就更新窗口是非法状态长度没有意义。第二种求最短合法窗口长度。典型如长度最小的子数组、最小覆盖子串。你要在收缩过程中、每次left移动之前更新答案。拿3.1来说当sum首次达到target时当前窗口是“以right为右端点的最短合法窗口”你试着收缩left如果收缩后依然合法那这个更短的窗口也要被记录下来。所以更新语句写在while循环内部而不是收缩完以后。第三种统计满足条件的子数组数量。典型如“和不超过target的子数组个数”。当收缩完成后窗口[left, right]是合法的并且因为数组全为正所有以right为右端点、左端点在left到right之间的窗口都合法所以这一轮对答案的贡献是right - left 1。这种题考察的是你能不能想明白“合法窗口的单调延续性”。三种题型用一个小表格总结题型答案更新位置原因最长合法窗口收缩完整后窗口合法后长度才有意义尽量保留长窗口最短合法窗口收缩过程中每次收缩前窗口合法且更短合法窗口数量收缩完整后以right结尾的所有合法窗口数量可一次算出2.3 复杂度与空间开销均摊思维的来源不定长滑动窗口的时间复杂度稳定在O(n)。这里不是每个循环都在O(1)里完成吗不是关键是left总移动次数。right每轮必然走一步总共n次left虽然可能在while里连续移动很多步但每个元素最多被移除一次所以left累计移动也不超过n次。right和left加起来总共移动2n次均摊到每一轮就是常数级别。空间开销取决于状态结构。如果字符集是固定的ASCII用一个长度128的数组就是O(1)空间如果用Python的Counter或字典空间是O(字符种类数)如果状态只是一个和那空间就是O(1)。这也是滑动窗口常被优先考虑的原因编码简单性能接近最优空间通常也不大。3. 三个经典题型完整拆解从暴力到滑窗的真实推导3.1 长度最小的子数组第一次接触“收缩”题目是这样的给定一个正整数数组nums和一个目标值target找出满足“和大于等于target”的长度最小的连续子数组如果不存在返回0。先看暴力怎么做。枚举子数组的左端点i和右端点j计算区间和判断是否大于等于target复杂度O(n³)用前缀和优化到O(n²)。问题出在哪大量重复计算——固定左端点i后右端点j每增加一个位置区间和都要重新算一遍。滑动窗口的推导靠一个关键观察数组元素全是正数所以固定left不动时随着right右移窗口和只增不减。一旦sum达到target对当前left来说这个right就是第一个合法右端点继续往后扩只会得到更长的窗口没必要再看了。此时正确的动作是收缩left把和降下来寻找更短的窗口。代码就非常清爽def minSubArrayLen(target: int, nums: List[int]) - int: n len(nums) left 0 total 0 ans n 1 # 用不可能的长度做初始值表示“无穷大” for right in range(n): total nums[right] # 右边界扩展 while total target and left right: ans min(ans, right - left 1) # 窗口合法记录并尝试收窄 total - nums[left] # 先更新状态 left 1 # 再移动左指针 return 0 if ans n 1 else ans这里有两个细节值得展开。第一为什么用while而不是if因为移除一个元素后total可能仍然大于等于target。比如target10窗口是[3,4,5]移除3后变成[4,5]和还是9不够了但如果窗口是[6,2,5]target8移除6后变成[2,5]依然合法就要继续移除。用while才能把所有更短合法窗口都遍历到。第二为什么更新写在while里面因为每执行一次移除操作之前窗口都是合法的而且比上一轮更短必须在这一刻参与比较。3.2 无重复字符的最长子串用频次计数维护合法性这道题的输入从数组换成了字符串要求找不含重复字符的最长子串长度。暴力写法是枚举所有子串再检查有没有重复字符复杂度O(n³)。用频次数组可以降到O(n²)但本质还是慢。滑动窗口的单调性在哪里固定leftright右移时窗口内某个字符的出现次数只可能增加不可能自动减少。所以一旦窗口里出现重复字符继续右扩永远不会消除重复必须移动left。维护一个频次数组cnt窗口扩展时给新字符计数1。出现重复时进入while循环不断将s[left]的计数-1同时left右移直到没有任何字符出现次数大于1。代码def lengthOfLongestSubstring(s: str) - int: n len(s) left 0 cnt [0] * 128 # ASCII字符集够用 ans 0 for right in range(n): ch s[right] cnt[ord(ch)] 1 while cnt[ord(ch)] 1 and left right: cnt[ord(s[left])] - 1 left 1 ans max(ans, right - left 1) return ans一个常用的小优化是while条件里只看s[right]这个字符的计数是否大于1。因为其他字符在之前已经被保证不超过1只有新加入的字符可能打破平衡所以不需要每次都遍历整个cnt数组判断有没有重复。这个小优化同样适用于很多窗口统计类题目。这道题的答案更新位置和3.1不同它在收缩完成之后更新。原因是窗口一旦有重复字符就是非法状态非法长度的最大值没有意义只有收缩到合法后窗口长度才代表“以right结尾的最长无重复子串”。3.3 最小覆盖子串把“合法状态”升级成缺口计数这是基础篇的压轴题也是最能检验你是否真正理解“状态设计”的一道题。题目给定字符串s和t在s里找一个最短子串要求包含t里的所有字符包括重复字符。比如tAABC窗口里必须至少有两个A、一个B、一个C。不存在就返回空串。如果直接用两个Counter每次判断窗口是否覆盖t都要遍历键复杂度会退化。正确做法是维护一个matched变量表示“当前窗口中有多少种字符已经达到了目标数量”。扩展右边界时新字符ch进入窗口窗口计数win[ch]加1。如果win[ch]恰好等于need[ch]说明这个字符从“不够”跨到了“刚够”matched加1。注意如果窗口里冗余到超出needmatched不会再变因为“满足”状态在跨过门槛那一刻就已经记录了。当matched等于need中不同字符的种类数时说明窗口完全覆盖t。这时进入收缩阶段在收缩循环里先记录当前窗口长度更新最短答案准备移除s[left]这个字符如果这个字符在need里有需求并且win中数量刚好等于need中的数量说明移除它会导致覆盖失效matched减1然后win[s[left]]减1left加1。代码def minWindow(s: str, t: str) - str: from collections import Counter need Counter(t) win Counter() matched 0 # 已达标的字符种类数 left 0 start 0 length len(s) 1 # 无穷大 for right, ch in enumerate(s): win[ch] 1 if need[ch] 0 and win[ch] need[ch]: matched 1 while matched len(need) and left right: if right - left 1 length: start left length right - left 1 remove_ch s[left] if need[remove_ch] 0 and win[remove_ch] need[remove_ch]: matched - 1 win[remove_ch] - 1 left 1 return if length len(s) 1 else s[start:start length]这段代码里最容易写错的点有两个。第一matched记录的是字符种类数不是字符总数。因为tAABC里需求是{A:2, B:1, C:1}种类数是3如果窗口里有2个A、1个B、1个C就算matched3而不是4。第二移除字符时判断win[remove_ch] need[remove_ch]必须发生在减1之前一旦先减了条件就变了matched会少算或多算。只要把3.1、3.2、3.3吃透后面遇到“至少有k个重复字符的最长子串”“最多k个不同字符的最长子串”等题目你只需要改一下valid的判断逻辑就行。4. 基础篇的坑状态更新顺序、空窗口与初始值4.1 先移除再移动一个顺序颠倒就全错的细节收缩左边界时标准的写法是total - nums[left] left 1也就是“先更新状态再移动指针”。如果你写反了left 1 total - nums[left] # 这里减的是已经移动后的left不是原来的元素结果就是漏掉了原left指向的那个元素状态和窗口对不上。这种错误在本地跑单测时特别隐蔽因为很多测试样例里数值碰巧也能通过但到了大数组上就再摇欲坠。我自己的习惯是——收缩时把“状态修改”和“指针移动”看成一个原子操作永远写在相邻的两行。有人喜欢用一行合并比如每次都写left 1之前更新状态也有人喜欢先移动再减nums[left - 1]。只要全程统一理论上都可以但对新手我强烈推荐“先减后移”因为逻辑上更贴合“移除当前left”不容易漏。4.2 while还是if收缩次数取决于单调性恢复的粒度间题里收缩操作用while还是if取决于一次移除能不能让状态恢复合法。3.1的和类型问题移除一个元素后很可能还是超过target要用while。3.2的重复字符问题如果窗口里只有一种字符重复移除到它只剩1个时可能就恢复了但窗口里也可能因为移动后其他字符变重复所以还是要用while。某些特殊题比如“最多两个不同字符的最长子串”一旦窗口变成三个不同字符移除一个字符就能让种类数降回2这时候用if也可以但为了通用性我仍然推荐先写while再按性能需要优化。基础篇不需要考虑if优化统一while会让逻辑更简单也减少出错面。4.3 空窗口语义与left right的保护收缩循环里写left right这个条件很多人不理解。考虑一种极端情况target很小all nums positiveright扩展一个元素后sum就超过target然后while开始收缩如果target非常小收缩到left right时窗口只有一个元素可能仍然满足条件继续收缩下去left会变成right 1窗口为空此时再执行total - nums[left]就越界了。所以收缩循环必须加上left right做保护。同时也要想清楚空窗口在这些题目里的语义长度为0的子串在“无重复字符”题里是合法候选吗通常不是在“最小覆盖子串”里空串也不满足覆盖条件。所以基础模板默认不把空窗口当合法结果如果需要处理空串要单独考虑。4.4 初始值设置与无解判断求最短窗口时初始值要设成一个不可能达到的长度比如n 1求最长窗口时初始值设成0。最后判断初始值是否被更新过就能区分“无解”和“有解”。3.1返回0当且仅当整个数组的和都不到target。3.3返回空串当且仅当length仍为len(s)1。3.2返回0当且仅当字符串为空。这个“用不可能值做初始值”的习惯能帮你规避很多“答案边界”问题。另外C和Java里如果求和用int注意total可能超过2^31-1建议用long long或longPython不需要担心。4.5 常见错误对照表错误类型现象正确做法收缩时先移动指针再更新状态漏元素结果错乱先更新状态再left 1求最短却在收缩后更新答案偏大在while循环内更新求最长却在收缩前更新可能记录非法窗口收缩完再更新缺少left right保护越界访问while条件加left right用固定长度k的思路套不定长思维卡壳复杂度爆炸先判断窗口长度是否由条件决定5. 学完基础篇之后下一步往哪走5.1 模板失效的第一个典型场景负数数组3.1强调“正整数数组”不是没道理。一旦数组里出现负数sum随right的增加不再单调之前的推导“非法后右扩没意义”就失效了。比如right扩展时加了一个负数sum反而变小原本不满足target的窗口可能重新变满足这时如果傻等left收缩就会错过潜在更优解。处理负数数组通常需要换工具想求“和等于k的最短子数组”可以用前缀和哈希表想求“和大于等于k且数组有负”的最短子数组问题复杂度会明显上升往往需要线段树等结构。基础篇阶段你只需要记住一句话滑动窗口模板成立的前提是合法性判断随right单调变化。一旦发现单调性被破坏不要硬套先回头重新分析。5.2 收缩方式可以更激进用索引跳跃代替逐格删除3.2用到了逐格删除。有些更快的写法会用哈希表记录每个字符最近一次出现的下标遇到重复时让left直接跳到重复字符上一次出现位置1不需要一格一格移除。这种写法代码更短、常数更小但它建立在对“窗口状态如何变化”的深刻理解之上。我的建议是基础篇先用逐格删除的通用模板因为它能不被任何优化假设绑架地适配所有题目。等你把状态维护练成肌肉记忆再去做索引跳跃的优化你会发现那只是把“移除过程”压缩了核心框架没变。5.3 定长与不定长的延伸领域网上一搜“滑动窗口”什么滑动窗口滤波、滑动窗口中位数、滑动窗口最大值最小值满屏都是但这些大多是定长窗口问题用的工具是单调队列、对顶堆基础模板完全不同。真正用不定长滑动窗口的工程场景更像是流式异常检测持续读入数据维护一个窗口当窗口内统计指标越界收缩左边直到恢复正常然后继续往后读。算法题里练的这套“先加后收、状态维护”的思路放到实时数据处理、日志分析、网络流量监控里同样成立。5.4 闭卷三遍这套模板只有写成肌肉记忆才算会说实话我带过不少人看这个专题最大的问题不是看不懂思路而是手写时状态更新顺序混乱。网上教程一眼扫过去觉得“懂了”合上屏幕自己写三分钟就卡在matched该不该减、答案该在哪更新。我的建议很直接把3.1、3.2、3.3三题关掉题解闭卷各写一遍。第一遍允许慢允许翻模板第二遍要求一次性通过第三遍试试不看模板十分钟写完。写完再回头看第4节的坑你会发现踩过的坑基本都写在里面。不定长滑动窗口的基础篇说到底就是四个字先加后收。把这个动作练成肌肉记忆后面那些花花绿绿的变体题都会变得顺理成章。