第一次在力扣上刷到最小覆盖子串这道题时我看到Hard标签心里是先打鼓的。但这道题绝对不能跳过因为它是滑动窗口专题里承上启下的一道题——窗口收缩的条件、字符计数器的维护、边界情况的处理全部在这一题里揉碎了。如果你正好刷到这一题或者刷完后面才发现自己根本没吃透那这篇整理就非常值得读一读。我不会给你贴一段代码就跑而是把这套统一化写法从头到尾拆开讲清楚每一步为什么这么写以及哪些地方新手十有八九会写错。1. 题目到底在求什么1.1 一个具体例子带你看懂题意题目描述其实很精简给你两个字符串s和t在s中找出包含t中所有字符的最短子串。关键点是“包含所有字符”并且要考虑字符的重复次数。比如t ABC那子串至少要有一个A、一个B、一个C如果t AABC那子串里必须有两个A、一个B、一个C少一个都不行。我拿一个典型例子来演示s ADOBECODEBANCt ABC。肉眼扫一遍最短的满足条件的子串是BANC长度是 4。ADOBEC也满足但长度为 6不是最短。注意CODEBA也满足条件但它并不是最短的而且它出现的位置靠后。这个例子的妙处在于你需要在一个较长的串里不断移动一段区间随时判断这段区间是否包住了t里的所有目标字符然后尝试压缩它。这里有一个非常重要的认知题里让你返回的不是满足条件的任意一个子串而是最短的那个。所以即便你找到了一个满足条件的窗口也不能立刻停手还要继续尝试让窗口变短。这就把问题从“找个答案”变成了“找最优答案”而滑动窗口恰好擅长处理这种场景。1.2 为什么暴力解法走不通如果没接触过滑动窗口第一反应往往是枚举s的所有子串判断每个子串是否包含t的所有字符然后记录最短的一个。这个思路本身没错但复杂度是灾难级的枚举所有起点和终点就是 O(n²)每个子串再统计字符出现次数又得 O(n)整体最坏情况是 O(n³)。对于s长度达到十万级别的用例这个复杂度基本等于超时。就算你用前缀和之类的技巧把字符统计优化到 O(1)枚举子串本身还是 O(n²)。力扣的测试用例设计得相当狠这种暴力写法在第 266 个用例附近就会被卡住。所以必须找到一个办法让每个字符最多被“进入窗口”和“离开窗口”各处理一次把总复杂度压到 O(n)。这个办法就是滑动窗口。1.3 什么样的问题适合滑动窗口滑动窗口不是万能的但它对一类问题极其有效在一个线性结构尤其是字符串和数组上寻找满足某种条件的连续子串或子数组并且这个条件随着区间扩大而单调变化。所谓“单调”是指当窗口向右扩展时它更容易满足条件当窗口左边界向右收缩时它更不容易满足条件。最小覆盖子串正好符合这个特征窗口越大覆盖的字符越多越容易包含t的所有字符窗口越小越容易丢失某些字符条件就越容易不满足。因为这种单调性我们才敢放心地移动两个指针而不必回退。后面讲模板时会看到这套逻辑不仅适用于这道题还能原样迁移到很多双指针题目上。2. 滑动窗口模板的四个关键设计2.1 双指针的移动规则统一化写法的核心骨架是维护两个指针left和right它们共同圈定一个区间[left, right)。这个区间左闭右开是刻意为之它能让代码里的长度计算特别干净窗口长度就是right - left不需要额外加一减一。规则只有两条右指针负责扩张左指针负责收缩。每一轮循环先把s[right]纳入窗口然后right当窗口满足题目条件时进入收缩阶段把s[left]移出窗口然后left。这里最反直觉的点是收缩用的 while 循环而不是 if。因为一旦窗口满足了条件它可能仍然有继续压缩的空间。比如s ADOBECODEBANC当右指针走到某个位置窗口同时包含A、B、C时左指针可以一口气越过好几个字符窗口依然满足条件直到再走一步就会破坏条件为止。这么设计的意义在于每一个位置作为窗口左边界时我们都能找到以它为起点的最短可行窗口然后记录全局最短。右指针不必为了每个左边界都从头扫描因为右指针只会向右移动。最坏情况下左右指针各遍历一次整个算法就是 O(n)。2.2 用什么数据结构记录字符状态这道题要求按字符出现次数判断覆盖关系所以哈希表是第一反应。我们需要两张表need记录t中每个字符需要出现的次数window记录当前窗口里每个字符实际出现的次数。C 可以用unordered_mapchar, intPython 可以用collections.Counter。这里有一个细节很多人没注意window表里不需要记录所有字符只需要记录那些出现在t里的字符。换句话说当右指针新纳入一个字符时先查它在不在need表里不在就直接忽略。这样做有两个好处一是省空间二是让后面valid计数器的逻辑变得清晰。如果你把所有字符都塞进window那判断条件的时候还得多一层过滤反而容易出 bug。2.3 valid 计数器的进阶作用如果窗口每次变化后都去遍历need表检查是不是每种字符都够了那复杂度又退化成了 O(n × 字符集大小)。优化思路是用一个整数valid记录“当前窗口中有多少种字符已经达到了需求数量”。每次右指针纳入一个字符c如果c在need中那么window[c]然后判断window[c]是否等于need[c]。如果相等说明这种字符终于凑齐了valid。同理收缩阶段移出字符d时如果window[d]减一前刚好等于need[d]说明减掉这个字符后它就不再满足需求valid--。这里最核心的判断条件是valid need.size()而不是valid t.size()。need.size()是t中不同字符的种类数比如t AABCneed.size()等于 2因为只需关注A和B两种字符是否都凑够。而t.size()是字符总个数那 4 个字符全部到位才算满足逻辑上完全说不通。我曾经见过不少人在这个判断上栽跟头最后代码在t含重复字符时返回错误答案。2.4 模板化的五步结构把上面所有设计串起来滑动窗口就变成了一个可以反复默写的五步结构初始化need表统计目标字符串中每个字符的出现次数。初始化left 0、right 0、valid 0以及记录最终答案的变量。外层 while 循环向右移动右指针把新字符纳入窗口并更新状态。内层 while 循环判断窗口是否满足条件满足则尝试更新答案并移动左指针收缩窗口。循环结束后根据记录的最优区间返回答案如果没有可行区间返回空串。这五步的普适性非常强。遇到其他滑动窗口题你只需要替换第 3 步里“更新状态”的具体逻辑以及第 4 步里“满足条件”的判断方式骨架完全不用动。这也是“统一化写法”这个名字的由来。3. C 完整实现与逐段剖析3.1 核心代码哈希表版来看完整实现。这是我用得很顺手的版本直接按照上面说的五步结构写class Solution { public: string minWindow(string s, string t) { if (t.empty()) return ; unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0, valid 0; int start 0, minLen INT_MAX; while (right s.size()) { char c s[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) { valid; } } while (valid need.size()) { if (right - left minLen) { minLen right - left; start left; } char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) { valid--; } window[d]--; } } } return minLen INT_MAX ? : s.substr(start, minLen); } };这段代码看着不长但每一行都有讲究。尤其要注意收缩阶段里valid--和window[d]--的顺序一定不能换。先用window[d] need[d]判断当前字符是否处于“恰好满足”的状态如果是则先让valid--再把window[d]减一。如果反过来先减少了window[d]接下来这个比较就永远不可能相等valid永远不更新整个算法直接失去正确性。3.2 为什么右指针扩展时要先判断 need扩展阶段代码是if (need.count(c)) { window[c]; if (window[c] need[c]) valid; }判断need.count(c)有两个作用。第一个作用是过滤掉t中不存在的字符它们不影响覆盖条件让它们白白增加window的计数只会让后续收缩逻辑变复杂。第二个作用实际上更重要保证window[c]和need[c]的比较有意义。need表里只有目标字符所以只对目标字符做计数比较是安全的。有同学可能会问如果c不在need里那它被右指针纳入窗口后是不是会永远留在窗口里不会。因为当窗口满足条件进入收缩阶段后左指针会把字符一个个移出去移出那些非目标字符时根本不会触碰valid。换句话说这些无关字符只是“路过”不会影响我们对最优解的判断。3.3 为什么收缩阶段顺序不能写反收缩阶段是本题最容易写错的部分我把完整逻辑再拆一遍char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) { valid--; } window[d]--; }首先要明确一个事实进入收缩阶段时窗口一定是满足覆盖条件的。也就是说此时valid need.size()每一种目标字符的数量都达到了需求。如果我们把左指针指向的字符d移出窗口只有两种情况会让条件被破坏d正好是目标字符并且它在窗口里的数量刚好等于需求数量。换句话说减掉这个d后它的数量就小于需求了种类数少了一种所以valid要减一。如果你先执行window[d]--那么window[d]就已经不等于need[d]了再执行if (window[d] need[d])自然永远为假valid就永远不减少。结果就是收缩循环停不下来最终窗口会被压缩成空串答案全错。这个 bug 虽然细微但极其常见我建议你把“先判断、后更新”这六个字刻在脑子里。3.4 复杂度与空间优化分析这个版本的时间复杂度是 O(n)其中n是s的长度。外层 while 循环右指针最多移动n次内层 while 循环左指针也最多移动n次合计 2n 次操作。每次操作在unordered_map上的读写是均摊 O(1) 的所以整体是线性复杂度。空间复杂度是 O(m)其中m是t中不同字符的个数因为need和window只存储这些字符的计数。如果追求极致性能还可以把哈希表换成固定大小的数组。因为题目限定只有英文字母和数字用int need[128]和int window[128]完全可以。注意这里不需要做need.count(c)判断改用need[c] 0即可因为不需要担心访问不存在的键。数组版的常数比哈希表小很多在苛刻的测试用例上能明显快出一截。但为了可读性我一般先用哈希表把逻辑写对再根据场景决定要不要换成数组。4. 我用 Python 重写时踩过的坑4.1 Python 版代码力扣刷题免不了要用 Python 写一遍尤其是面试时手撕代码Python 的简洁语法特别占优势。但用 Python 写这道题有一些和 C 完全不同的坑。先看代码class Solution: def minWindow(self, s: str, t: str) - str: from collections import Counter if not t: return need Counter(t) window Counter() left, right 0, 0 valid 0 start, min_len 0, 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 len(need): 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]如果用Counter访问不存在的键默认返回 0所以window[c] 1和window[d] - 1不需要担心 KeyError。但有两点要特别提醒valid len(need)里len(need)是不同字符的种类数这一点和 C 完全一致。另外如果不小心用了普通dict而不是Counter那么window[c] 1在c第一次出现时会抛异常。这类问题在面试现场遇到会非常影响心态。4.2 常见错误排查表把各种写错的情况整理成一张速查表方便你写完代码后对照自查错误现象根本原因解决办法返回空串但输入明显有解valid的判断条件误用len(t)改成len(need)即不同字符的种类数结果比正确答案长收缩阶段使用了 if 而不是 while把收缩逻辑放在 while 循环里直到条件被破坏收缩后 valid 不减陷入死循环先window[d]--再判断是否等于need[d]先判断window[d] need[d]再执行计数自减目标字符数量不够时提前收缩valid初值设置错误或更新逻辑漏分支确认右指针扩展和左指针收缩两个分支都更新 validPython 直接抛 KeyError用了普通 dict 存储窗口计数改用collections.Counter或者用window.get(c, 0)超时每次判断条件时都遍历 need 表用 valid 整数计数器把条件判断压到 O(1)这张表里的前四条几乎覆盖了滑动窗口题 90% 的常见 bug。特别是第一条和第二条我见过太多次了都是对“窗口满足条件”的定义不够清晰导致的。4.3 边界条件专项测试有些边界条件不测不知道一测吓一跳。我建议你把下面这几组输入都跑一遍s t A应该返回空串因为 s 根本不够长。s At 题目虽然没说 t 一定非空但稳妥起见代码开头直接判空返回空串。s At AAs 里只有一个 A凑不齐两个 A应该返回空串。s ADOBECODEBANCt ABC答案应该是BANC而不是ADOBEC。s aat aa答案应该是整个串aa这类用例最容易验证重复字符的处理。s at a答案应该是a单字符匹配是基本盘。上面几组用例跑通了这道题的正确性基本就有了保障。我刷题的习惯是写完代码先用这些边界用例过一遍脑子再提交到力扣上这样能省下不少 WA 后调试的时间。5. 滑动窗口统一模板的迁移实战5.1 变体题一字符串的排列力扣第 567 题“字符串的排列”判断s2中是否包含s1的某个排列也就是是否存在一个窗口使得窗口内各字符数量恰好等于s1中对应字符的数量。这题的模板和 76 题几乎一模一样区别有两点。第一答案判断不是“最短”而是“是否存在”第二窗口长度是固定值等于s1的长度。实际操作时右指针每扩展一次如果当前窗口长度超过len(s1)就强制收缩一个单位然后再判断valid len(need)。一旦条件成立立即返回 true。这里的收缩不再是“尽可能收缩到最小”而是“保持窗口长度为定值”。但模板的五步结构没有变初始化 need移动右指针更新 window 和 valid移动左指针维护状态判断条件。5.2 变体题二找到字符串中所有字母异位词力扣第 438 题要求返回所有异位词的起始索引核心思路和 567 题完全一致只不过每找到一个满足条件的定长窗口不是立即返回而是把当前的left记录到结果列表里。代码甚至可以直接复用维护固定长度窗口条件满足时产出一个下标然后继续进行。这道题能让你更直观地理解滑动窗口的模板关心的是两个“换”字。一是换掉“窗口满足条件”的判断逻辑二是换掉“窗口不满足条件时左指针如何移动”的规则。只要这两处清楚了所有相关题目都是同一套骨架。5.3 变体题三无重复字符的最长子串力扣第 3 题是另一个极端的变体。它没有外部目标串t所以不需要need表。窗口内只要出现任何重复字符就违反了条件。这时候我们用一个window表记录窗口内每个字符的出现次数一旦某个字符计数大于 1就说明有了重复需要移动左指针直到它重新变成 1。在这个问题里“窗口满足条件”的定义从“valid need.size()”变成了“window 中没有任何字符出现次数大于 1”。你可能说这和 76 题差别很大呀其实模板没变右指针扩展、更新状态、while 判断条件、左指针收缩、记录答案。变的只是第 3 步和第 4 步的具体逻辑而已。5.4 迁移模板的“三个换两处”法则综合上面几个变体我总结出一套迁移模板的实操心法“三个换两处”。三个不变的内核是右指针只管扩展左指针只在条件满足时收缩每次收缩前先记录当前窗口状态。两个必换的位置是状态更新的逻辑以及窗口满足条件的判断逻辑。以第 76 题为例状态更新是维护window和valid满足条件是valid need.size()。到了第 3 题状态更新变成维护一个简单的window计数表满足条件是window[c] 1。到了第 209 题“长度最小的子数组”状态更新变成一个整数sum满足条件是sum target。框架不变变化的是数据结构和判断语句这就是统一化写法的价值。我个人平时做滑动窗口题会先在草稿纸上默写一遍五步模板然后才开始写具体逻辑。遇到没见过的题也不慌先想清楚窗口里维护什么信息、什么条件触发收缩、收缩到何时停止这三问题一答代码基本就成型了。这道第 76 题是检验这套方法的最好试金石多花点时间把它的每一处细节吃透后面再刷滑动窗口专题会顺手很多。