滑动窗口统一化模板：从最小覆盖子串吃透双指针算法

1. 先把最小覆盖子串这个题吃得透透的1.1 题面到底在说什么很多人第一眼看到力扣第 76 题《最小覆盖子串》时会觉得这是一道“很绕”的难题。题面其实很简单给你两个字符串s和t要你在s里找一段最短的连续子串让它“覆盖”字符串t。这里的“覆盖”不是子序列那种跳过式匹配而是子串里的字符数量必须能包住t里的字符数量。比如t AABC那窗口中必须至少有两个A、一个B、一个C缺任何一个都不算覆盖。光看到“连续子串 覆盖”两个词就该意识到滑动窗口是首选思路。但为什么还有不少人写不出来因为这道题难在两个地方第一t里可能有重复字符不能用简单的“字符集合包含”来判断第二要求的是“最短”所以窗口一旦满足条件就要不停尝试收缩左边而不是停下来。这两个点不弄清楚代码一写长就容易乱。这题在 LeetCode 上被标为 Hard但它在实际面试里更像“必须熟练掌握”的题目因为滑动窗口本身就是字符串题里最高频的套路之一。把 76 题吃透后面 3、438、567、30、159 这类题都会变得很顺所以很值得花时间把统一化写法练扎实。1.2 为什么暴力枚举会直接阵亡最容易想到的暴力做法是两层循环枚举所有子串的起点和终点然后对每个子串统计字符频次再和t的频次表比较。假设s长度为nt长度为m这种写法的时间复杂度是O(n^2 * m)如果再加上字符集大小C可以写成O(n^2 * C)。n一旦到十万级别这个复杂度是完全不可接受的。更重要的问题在于暴力法没有利用窗口变化的连续性。想象一下当右指针从right移到right1时窗口只多了一个字符其他字符的计数完全没变。如果每次重新统计窗口等于把已经算过的东西反复推倒重来。滑动窗口的核心思想就是让窗口状态增量更新右指针加字符、左指针减字符每一步只处理两个位置上的字符这样整体才能做到线性时间。2. 滑动窗口统一化写法先建立肌肉记忆2.1 从两个指针到“窗口对象”统一化写法首先要定义清楚窗口的表示方式。一般用两个下标left和right维护一个左闭右开区间[left, right)。为什么是左闭右开因为right - left可以直接得到窗口长度而且初始化为left 0, right 0时窗口是空区间后面每加入s[right]再让right 1语义非常自然。很多人习惯一开始把right设为 1写起来反而容易在边界上出错。窗口里维护什么对最小覆盖子串来说需要维护当前窗口内每个字符出现的次数。有人习惯用数组[0] * 128也有人喜欢用字典。统一化模板默认用字典因为字典更能表达“只有t里出现过的字符才有资格参与判断”这个逻辑而且换到其他字符集都不用改结构。为了不因为访问不存在的 key 报错可以配合collections.defaultdict(int)使用但这只是工程上的便利真正核心的是如何用一个状态变量判断窗口是否满足覆盖条件。2.2 用一个整数 valid 表示“满足状态”如果每次判断窗口是否覆盖t都遍历t的频次字典逐个比较代码虽然也能跑但效率低而且显得很笨。更优雅的做法是维护一个整数valid它表示“当前窗口已经满足了几种字符的需求”。为什么是“种类数”而不是“字符总数”因为t AABC时t里有 3 种字符A、B、C其中A需要 2 个B需要 1 个C需要 1 个。如果窗口里出现A:2, B:1, C:1那这 3 种都已经达标valid 3如果窗口变成A:5, B:1, C:1A 已经远超所需但“A 这个种类是否达标”这件事早就记过了valid依然只能是 3不会变成 6。这个设定就是整个模板的关键所在。具体来说当右指针把某个字符c加入窗口时只有window[c] need[c]的这一瞬间valid才加 1。为什么一定要求相等而不是因为一旦字符数量超过需求说明它已经达标过valid里已经加了 1如果再用大于等于去判断同一个字符会反复触发valid 1最后valid就会被撑爆窗口永远无法正常收缩。反过来当左指针移除字符时只有window[d] need[d]的这一瞬间valid才减 1。这个“相等即翻转”的设计是整个模板最容易写错、也最值得记住的地方。2.3 统一化模板的长相把上面的逻辑整理成统一的滑动窗口框架大概是这个样子初始化 left right 0 初始化 need 字典、window 字典、valid 0 初始化答案区间 while right len(s): c s[right] right 1 更新 window[c] if c 是 need 中的字符 and window[c] need[c]: valid 1 while valid len(need): 用当前窗口更新答案 d s[left] left 1 把 d 从 window 中移除 if d 是 need 中的字符 and window[d] need[d]: valid - 1这里仍然沿用了while right len(s)的风格因为这样的left、right都要自己维护后面做题可以保持统一。对于最小覆盖子串这种“找最短”的问题答案更新放在收缩循环里面而对于“找最长”的问题答案更新通常放在右指针扩张完成后、收缩条件触发前。这个差别很重要后面第 6 章会专门说明。3. 完整实现与代码细节3.1 Python 实现逐行拆解直接上一份可以提交的 Python 代码每一行都是踩过坑之后磨出来的from collections import defaultdict class Solution: def minWindow(self, s: str, t: str) - str: if not s or not t: return need defaultdict(int) for ch in t: need[ch] 1 need_cnt len(need) window defaultdict(int) valid 0 left 0 right 0 start 0 min_len float(inf) while right len(s): c s[right] right 1 if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid need_cnt: if right - left min_len: min_len right - left start left d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return if min_len float(inf) else s[start:start min_len]这段代码的核心逻辑分三步。第一步构建need字典记录t中每个字符需要的数量同时用need_cnt保存不同字符的种类数。注意这里不是len(t)因为valid比较的是种类数。第二步右指针扩张。每来一个新字符c如果它出现在need里就更新window[c]并且在恰好达到需求数量时让valid 1。c不在need里时直接忽略它对valid的影响但窗口本身还在扩张。第三步收缩左边界。只要valid need_cnt就说明当前窗口已经覆盖了t。此时先记录长度再把左指针往右移。移出窗口的字符d如果存在于need中先判断window[d] need[d]如果成立则valid - 1最后再把window[d]减掉。这里的顺序千万不能反。3.2 为什么“先减 valid 再减 window”不可交换这个点值得多花两分钟讲。假设need里A需要 2 个当前窗口中A正好是 2 个此时这个字符是达标的valid已经把这个种类算进去了。现在左指针指向一个A我们要把它移出窗口。如果先执行window[d] - 1窗口里A变成 1 个然后代码再去判断if window[d] need[d]发现1 ! 2于是valid不会减 1。但窗口实际上已经不再满足A的需求了valid却不更新结果就是整个判断系统错乱甚至可能出现死循环。反过来先判断window[d] need[d]此时A还是 2 个等于need的 2因此valid先减成 0然后window[d]再变成 1一切就都合理了。这个坑用sAAB, tAA一测就能暴露。错误的版本可能在最后返回AAB而不是AA因为valid一直不归零收缩逻辑完全失效。所有用valid做“种类达标”标记的滑动窗口题都必须遵守这个顺序在修改window计数之前判断相等而不是修改之后再判断。3.3 Java 版本可以怎么写面试时如果要求用 Java其实只是把字典操作换一下public String minWindow(String s, String t) { if (s.length() 0 || t.length() 0) return ; MapCharacter, Integer need new HashMap(); for (char ch : t.toCharArray()) { need.put(ch, need.getOrDefault(ch, 0) 1); } MapCharacter, Integer window new HashMap(); int valid 0; int left 0, right 0; int start 0, minLen Integer.MAX_VALUE; while (right s.length()) { char c s.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).intValue() need.get(c).intValue()) { valid; } } while (valid need.size()) { if (right - left minLen) { minLen right - left; start left; } char d s.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).intValue() need.get(d).intValue()) { valid--; } window.put(d, window.get(d) - 1); } } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); }Java 版本的Integer对象在比较时小范围会走缓存直接在大部分情况下没问题但最稳妥的做法还是用.intValue()拆箱后再比较。另外need.size()就是种类数和 Python 里的len(need)是一个意思。4. 实操细节与参数计算4.1 窗口收缩时“更新答案”的时机这个题有一个非常容易踩的细节答案到底应该在哪里更新很多初学者会在右指针扩张的while循环外面只做一次判断然后尝试用left移动来确定结果。但这么做很可能漏掉最优解。原因很简单当右指针固定时窗口可能从某个较长的覆盖状态一路收缩到刚好不覆盖这个过程里存在多个合法窗口最短的那个可能出现在收缩到临界点之前的某一次left移动之后。所以在while valid need_cnt的循环体内部每移动一次left都应该用当前的right - left去更新一次答案。这样能保证所有合法窗口都不会被跳过。还有一个细节是“先更新答案再移动 left”。有些版本会把更新放在收缩循环之后比如先收缩到不合法再记录上一次的状态这样也能对但要额外保存“上一次 state”的信息代码容易乱。统一化模板的做法是每走一步收缩都记录最直接、最不会漏。4.2 为什么window[c] need[c]而不是前面已经提过相等判断是为了避免valid重复计数这里再从另一个角度解释一遍。valid本质上是“哪些字符已经达标”的计数器。一个字符只有两种状态达标和不达标。当窗口里该字符数量从“不达标”跨到“达标”的那一瞬间状态翻转valid加 1从“达标”掉回“不达标”的那一瞬间状态翻转valid减 1。其他任何时刻无论超出数量多少状态都不变。如果你用相当于每次看见“达标”就加 1而不是在状态翻转时加 1。比如窗口里A已经 5 个need里需要 2 个每次加入A都会触发一次valid 1那valid早就超过need_cnt了后面的while valid need_cnt永远不可能成立。这是写完代码后最容易出现“运行很久但结果为空”的原因之一。4.3 时间复杂度计算不要被 while 骗了外层是right从 0 扫到n-1内层看起来是一个可以连续执行的while很多初学者会担心这是不是O(n^2)。分析的关键在于left的移动范围left 只会从左往右移动而且永远不会回头。right 每移动一步left 最多也只会移动若干步但 left 在整个算法中移动的总次数不会超过n。所以把 right 的n次移动和 left 的总共至多n次移动加起来是2n级别的操作整体复杂度就是O(n)。再加上一开始构建need字典需要遍历t时间复杂度O(m)所以完整的时间复杂度是O(m n)。空间上两个字典的大小不超过字符集大小对于英文字母来说是O(1)更通用的说法是O(字符集大小)也就是O(1)。这个复杂度在面试里是要能清晰讲出来的。5. 常见问题与排查技巧实录5.1 常见错误valid 当成了窗口里匹配字符总个数valid这个变量名很容易让人误以为它是“匹配上的字符总数”。我见过不少人把t AAB的例子拿来做测试窗口里出现A:3, B:1时他们觉得已经有 4 个字符匹配上了valid应该很大。但按模板的定义valid只记录“A 这种字符是否达标”和“B 这种字符是否达标”它永远不可能超过len(need)。这个理解如果不纠正后面所有基于while valid need_cnt的代码都会变得难以调试。建议在草稿纸上手动模拟几轮need里A:2, B:1need_cnt 2窗口从空开始加入A时 valid 不变再加入A时 valid 变 1加入B时 valid 变 2这时才触发收缩。每个字符只贡献一次而不是一个字符算一次匹配。5.2 常见错误忘记判断字符是否在 need 中如果用defaultdict(int)访问不存在的 key 不会报错但代码逻辑容易变脏。比如窗口遇到一个字符x它根本不在t里如果也执行window[x] 1然后判断window[x] need[x]由于need[x]是 0window[x]是 1不会相等valid不会变程序能跑。但问题在于window字典里塞了大量无关字符后续调试、打日志都会干扰视线。更推荐的做法是右指针加入字符时先if c in need只处理需要的字符左指针移除字符时同样if d in need。这样代码的语义更清晰也避免了普通字典KeyError的隐患。养成这个习惯之后迁移到其他题时也会自然沿用。5.3 边界条件空串、超长、重复字符题目虽然通常保证t非空但健壮的解法还是要在开头处理not s or not t。另外如果len(t) len(s)其实可以直接返回空串因为s的长度都不够。虽然不加这个判断也能通过但加上之后能提前剪掉大量无效计算面试时也是一个加分项。还有一类边界是重复字符。t aa、s a时窗口永远无法满足A出现两次的需求最终应该返回空串。很多人会因为代码里valid一直到不了need_cnt导致start和min_len从未更新最后返回s[0:0]其实也是空串但为了可读性最好显式判断min_len是否还是float(inf)如果是就返回。5.4 排查技巧三组黄金测试用例调试这类题时不要上来就跑长字符串而是准备几个专门验证逻辑的最小样例。下面这张表我用了很久几乎每次写滑动窗口都会拿出来过一遍测试输入期望输出排查目标sa, taa单字符基本流程sa, taa覆盖不足时的返回逻辑sAAB, tAAAA重复字符和 valid 翻转顺序sADOBECODEBANC, tABCBANC官方样例收缩时机sbba, tabba起点不是窗口左边界的情况sabc, tabcdt 比 s 长时的退出尤其是AAB这个样例是验证“先减 valid 再减 window”顺序的试金石。如果代码里顺序写反这个样例基本必挂。6. 把统一化写法迁移到其他滑动窗口题6.1 先总结模板迁移的关键这套模板之所以叫“统一化”是因为它把滑动窗口题的几个关键决策点抽象得非常清楚。遇到新题时不要急着背代码先回答四个问题窗口容器里装什么最常见的是字符频次字典也可能是一个数值、一个 set、一段区间。什么叫“满足题意”把它抽象成一个valid或者其他布尔状态尽量做到 O(1) 维护。什么时候收缩最小覆盖类问题是“满足条件时收缩”最长无重复类问题是“违规时收缩”。什么时候更新答案找最短在收缩循环内部更新找最长在收缩完成后的合法状态更新。想清楚这四个问题再看代码你会发现 76、3、438、567 这些题的长相都极其相似差别只是几个判断条件。6.2 一个表看懂同类题目的调整题目窗口容器满足条件收缩条件答案更新时机76 最小覆盖子串字符频次字典valid need_cnt窗口满足覆盖条件收缩时每步更新最短3 无重复字符的最长子串字符频次/set窗口内无重复字符出现重复字符收缩完成后更新最长438 找所有字母异位词字符频次字典valid need_cnt窗口长度超过len(p)长度等于len(p)时记录起点567 字符串的排列字符频次字典valid need_cnt窗口长度超过len(t)长度等于len(t)时返回 true拿第 3 题“无重复字符的最长子串”来说它的窗口里维护的也是字符频次但状态不是“覆盖所有需求”而是“窗口里没有任意一个字符的频次大于 1”。一旦某个字符出现次数超过 1就说明重复了需要收缩左边界直到把重复的那个字符挤出窗口。因为求的是最长所以答案一般在收缩完成后、窗口重新合法的那一刻更新。再拿第 438 题“找到字符串中所有字母异位词”来说本质上就是固定窗口长度的 76 题。窗口长度必须等于len(p)所以收缩条件不是“已经覆盖”而是“窗口长度超过了目标长度”。当valid need_cnt并且right - left len(p)时当前起点就是一个答案。6.3 个人建议用这套方法刷一个题单从 76 题出发我建议按顺序刷76 → 3 → 438 → 567 → 30 → 159 → 340。刷的时候不要直接看题解先在草稿纸上写四个元素容器、状态、收缩、更新。哪怕一开始写错了再对照自己的模板你会很快发现它们的核心骨架完全一致变的只是几个条件。说点实际的我在刷题群里见过太多人把 76 题写成了“套模板但不知道为什么模板长这样”的样子。只要把valid这个变量的设计理解透了后面 438、567 基本可以二十分钟内写出来。这个细节本质上是把一个“子串是否合法”的判断从 O(K) 降到了 O(1)也是滑动窗口能在线性时间里跑起来的根本原因。个人体会滑动窗口的统一化写法不是万能的公式但它是字符串子串问题里性价比最高的一种思考框架。你不需要记住每一道题的代码只需要记住“用窗口维护状态、用状态驱动收缩、按目标决定更新答案”这条主线剩下的细节都交给测试用例去逼出来就好。