前阵子有个朋友去面试被问了一道字符串里找最短覆盖子串的题回来跟我说Minimum Window Substring这题看着并不难但一上手就发现窗口该什么时候缩、怎么判断已经覆盖了全是坑。我跟他聊完发现很多人都是卡在滑动窗口这个思路的细节落实上——知道要用双指针但写出来的代码要么超时要么边界错。这题是LeetCode 76也是LeetCode 100 hot里的常客刷题指南里基本绕不开。这篇就用完整的思路拆解、代码实现和实测教训把这道题彻底讲透。题目本身的描述很简洁给你一个字符串s、一个字符串t要在s里面找出包含t全部字符的最短子串。注意是包含t的全部字符不是包含t这个子串。也就是说t里的字符可以在s的子串里以任意顺序出现而且如果t里有重复字符子串里也要有对应数量的重复字符才算覆盖。如果你已经会用双指针写无重复字符的最长子串这类题这题看起来只是换了个方向收缩但实际写起来会发现完全不是一回事。这篇文章我会从题目约束开始讲到为什么滑动窗口是正解再到完整的可运行代码和踩坑记录最后延伸到这类题目的通用套路争取让不同基础的人都能看明白。1. 题目到底在问什么约束条件决定了解法方向很多人看到这道题第一反应是用哈希表统计t然后遍历所有子串这思路没错但完全没考虑复杂度。要理解为什么这题必须用滑动窗口而不是别的办法得先把题目的约束条件看透。1.1 题面、示例与最容易被忽略的覆盖定义先看题面。给定一个字符串s一个字符串t返回s中涵盖t所有字符的最小子串。如果s中不存在这样的子串返回空字符串。官方给的示例是输入: s ADOBECODEBANC, t ABC 输出: BANC这个例子里最短的覆盖子串是BANC长度为4。注意ADOBEC也覆盖了ABC但长度是6比BANC长所以不是答案。涵盖t所有字符到底是什么意思这里有三个隐藏规则顺序无关子串里的字符不需要和t中的顺序一致。比如t ABCs BAC的任意包含这三个字符的子串都算覆盖。重复计数t中的重复字符在子串中也必须出现足够的次数。比如t AABC子串必须至少包含两个A、一个B、一个C缺一个A都不算覆盖。额外字符允许子串可以包含t中没有的字符这些字符不影响覆盖判定。比如s ADOBECODEBANC中BANC里的N不在t中但子串依然覆盖。这三条规则就是整个题目的核心语义。很多错误写法都是因为忽略了第二条——只在t中的字符计数上做了判断但在窗口收缩时没有正确维护重复字符的计数。1.2 字符集范围一个决定实现方式的关键细节题目对字符范围有明确约束s和t由英文字母组成但注意题目的标准表述是英文字母大小写都有。这是个影响实现方式的细节。如果只包含小写字母那用一个长度为26的数组来计数就行非常轻松。但如果大小写都有就是52个字符。更通用的做法是假设任意ASCII字符128个甚至Unicode字符。LeetCode的测试用例里这两种情况都可能出现所以写代码时直接把计数结构做成能处理任意字符会比较稳。我见过不少人在这里翻车用一个长度为26的数组结果遇到大写字母就直接越界或者认为只有小写字母导致某些隐藏测试用例失败。实际上LeetCode这道题的输入范围是英文字母但s和t都有可能包含大写和小写稳妥起见计数数组开到128覆盖所有ASCII字符是最省心的做法或者直接用HashMap/Counter。字符集范围会影响时间复杂度的常数但不影响算法本身的量级。比如用数组计数访问是O(1)用哈希表计数访问平均也是O(1)。但数组的方式常数更小运行更快这在LeetCode的耗时排名上是有直观体现的。1.3 暴力解的时间账单为什么必须放弃假设我们先不考虑效率用最直观的暴力法枚举s的所有子串对每个子串判断是否覆盖t。枚举所有子串的数量是O(n^2)每个子串长度为O(n)统计子串中每个字符出现次数需要O(n)时间和t的计数比较又需要O(m)时间m是t的长度。所以总复杂度是O(n^3)级别。如果s的长度是10万LeetCode的测试用例确实可以达到这个量级n^3的计算量是天文数字根本跑不完。这就是为什么暴力法在算法题里只能作为理解题意的辅助手段不能作为正式解法。从这个复杂度账单能看出优化方向上只有两条路要么减少枚举子串的数量要么降低判断覆盖的时间。滑动窗口同时解决了这两个问题窗口移动的总次数是O(n)覆盖判断通过维护一个计数器变成O(1)。后面会详细展开。2. 为什么滑动窗口是这题的正解从暴力法的时间账单说起滑动窗口不是一个高深莫测的算法它的本质是用两个指针维护一个区间根据条件动态调整区间起点和终点。但要搞清楚为什么它适合这题得先从暴力法的劣势开始分析。2.1 暴力法的实际成本重复计算是最大的浪费暴力法的关键浪费在于当我们枚举子串s[i..j]和s[i..j1]时后者比前者只多了一个字符但我们依然从头开始统计后者的所有字符出现次数。这太浪费了。举个例子s ADOBECODEBANC枚举子串ADOBE和ADOBEC后者就是前者加了一个C。如果重新统计ADOBEC里每个字符的次数那A、D、O、B、E这五个字符的计数等于白算了一遍。增量更新的思想在这里非常自然每次只更新新加入的那个字符的计数而不是重新统计整个子串。这是从暴力法走向滑动窗口的第一步认知。2.2 滑动窗口的本质两个指针维护区间增量更新状态滑动窗口的框架是右指针right不断向右扩展扩大窗口范围当窗口已经覆盖了t中的所有字符时尝试移动左指针left向右收缩尽量缩短窗口长度一旦收缩到不满足覆盖条件就停下来继续移动右指针。整个过程像一条毛毛虫在绳子上爬行左边界和右边界交替前进。这样做的核心收益有两方面每个字符最多被右指针访问一次、被左指针访问一次。总移动次数是O(n)而不是O(n^2)。通过维护一个当前窗口中有多少个字符已经满足了t的要求的计数器判断窗口是否覆盖t的时间从O(m)降到了O(1)。关于第二点很多人写这题时的困惑是每次判断窗口是否覆盖t难道不需要重新遍历t的所有字符检查它们在窗口中的计数是否达标吗如果这样做那又变回O(n^2)了。正确做法是维护一个变量matched有的叫formed记录当前窗口内已经达到t所需数量的字符种类数。当matched len(t的字符种类数)时说明窗口已经覆盖了t。这个变量的更新在每次右指针扩窗和左指针收缩时同步进行都是O(1)操作。2.3 这道题和无重复字符最长子串的本质区别很多人之前刷过LeetCode 3无重复字符的最长子串那道题也是滑动窗口但两道题在窗口收缩的逻辑上有个重要区别如果不区分清楚做76题时会踩坑。在LeetCode 3里窗口内不能有重复字符所以一旦右指针指向的字符已经在窗口内就必须收缩左指针直到该字符离开窗口。那道题只有一个约束条件且约束是硬性的——窗口内不能有重复字符。而在76题里窗口的覆盖条件是软性的——窗口内允许有任意数量的额外字符只要t中的字符都出现足够次数就行。所以收缩左指针的时机不是右指针字符重复了而是左指针指向的字符在移出窗口后窗口仍然保持对t的覆盖。这个判断需要用到该字符在t中是否有要求以及移出后数量是否仍然达标。我见过不少初学者把这两道题的收缩逻辑混在一起结果就是窗口缩过头了或者不知道怎么判断还能不能继续缩。后面写代码时我会用具体的例子说明这个区别。3. 写代码前的三个关键决策计数、判定与收缩时机确定用滑动窗口之后接下来就是几个关键的实现决策。这些决策直接决定代码的简洁度和运行效率。我建议你在写代码之前先把这三个问题想清楚否则很容易写出逻辑绕来绕去还不对的版本。3.1 计数结构用数组还是哈希表统计t中每个字符的需求量主流做法有两种方案实现时间复杂度空间复杂度优点缺点数组计数int[] need new int[128]O(1) 更新O(128) O(1)访问快常数小得知道字符范围字符集很大时浪费空间哈希表计数MapCharacter, IntegerO(1) 平均O(m)灵活适合任意字符集常数较大代码相对繁琐我个人在LeetCode 76的题解里更喜欢用数组因为题目输入已经限定为英文字母大小写数组开到128完全够用。假如你是为了应对面试可以先问面试官字符集范围如果对方说任意ASCII字符数组方案依然是安全的。如果扩大到Unicode那哈希表更合适。用数组时有个小技巧数组的下标直接用字符的ASCII码比如need[A]。虽然A的数值是65但Java和Python这种语言都允许用字符作为数组下标Python用字典时无所谓Java的数组下标必须是int但char会自动转成int。这样写的好处是代码可读性高不用手动做c - A的换算。3.2 窗口是否覆盖的判断如何做到O(1)窗口覆盖t的判断最笨的方法是每次都用t的字符集遍历一遍检查窗口内每个字符的计数是否都大于等于需求量。但这样每移动一次指针就要O(m)时间总体会变成O(n*m)虽然比O(n^2)好一些但不够优雅而且在m很大时也可能超时。标准做法是维护一个变量比如叫matched或covered表示当前窗口内已经满足需求的字符种类数。它和t中的字符种类数比较。当两者相等时窗口就覆盖了t。具体维护逻辑是这样的右指针right指向的字符c进入窗口window[c]加1。如果window[c] need[c]说明字符c在窗口里的数量已经达标matched加1。左指针left指向的字符c移出窗口window[c]减1。如果window[c] need[c]注意是减之前等于need[c]减之后小于说明字符c的数量不再达标matched减1。这里有个容易绕晕的点为什么右指针扩展时是等于才matched左指针收缩时是小于才matched--因为matched记录的是达标的字符种类数每种字符只有达到需求量和没达到需求量两个状态。当window[c]从need[c] - 1变成need[c]就是从不达标变成达标的瞬间这时才需要更新matched。反过来当window[c]从need[c]变成need[c] - 1就是达标变成不达标的瞬间这时才matched--。很多错误的代码就是在这里多写或少写了判断条件导致matched计数不准最后整个逻辑错乱。3.3 收缩左指针时的状态回滚细节当窗口覆盖t时我们需要记录当前窗口长度和起始位置然后尝试收缩左指针。收缩时有一个经典错误直接移动left但忘记同步更新window数组和matched变量。这会导致后续判断全部出错。正确的收缩流程是记录当前窗口长度len right - left 1如果比已记录的最短长度还要短更新最短长度和起始位置。将left指向的字符c从window中移除window[c]--。如果移除后window[c] need[c]说明字符c不再达标matched--。将left右移一位。重复上述过程直到matched required即窗口不再覆盖t。这里还有一个细节很多人没注意如果left指向的字符c根本不在t中那么need[c]为0无论window[c]是多少移除后都不会出现window[c] need[c]所以matched不会变化窗口可以继续收缩。这说明额外字符不会阻塞收缩过程和前面讲的额外字符允许语义一致。状态回滚看起来简单但在写代码时很容易漏掉第3步。我当时第一次写这题时就是漏了这步导致收缩一次后matched没有及时减1窗口明明已经不覆盖了程序还以为覆盖结果答案错误。后来我专门把这三步流程写在注释里才彻底理清。4. 完整实现与逐段拆解两个指针滑动出最优解下面给出一个经过实测的Python实现以及对应的Java版本。Python版本比较好读适合理解算法逻辑Java版本适合提交到LeetCode时追求更快的运行速度。4.1 Python参考实现def minWindow(s: str, t: str) - str: if len(s) len(t): return # 统计 t 中每个字符的需求量 need [0] * 128 for ch in t: need[ord(ch)] 1 required len(set(t)) # t 中有多少种不同字符 window [0] * 128 # 当前窗口内每个字符的出现次数 matched 0 # 当前窗口中已经达标达到需求量的字符种类数 left 0 min_len float(inf) start 0 # 右指针向右扩展窗口 for right in range(len(s)): c s[right] window[ord(c)] 1 # 如果 c 在 t 中且窗口内 c 的数量刚刚达到需求量则 matched 加 1 if need[ord(c)] 0 and window[ord(c)] need[ord(c)]: matched 1 # 当窗口覆盖 t 时尝试收缩左边界 while matched required: cur_len right - left 1 if cur_len min_len: min_len cur_len start left # 左指针右移前先把 left 指向的字符移出窗口 left_char s[left] window[ord(left_char)] - 1 if need[ord(left_char)] 0 and window[ord(left_char)] need[ord(left_char)]: matched - 1 left 1 if min_len float(inf): return return s[start:start min_len]4.2 Java参考实现class Solution { public String minWindow(String s, String t) { if (s.length() t.length()) { return ; } int[] need new int[128]; for (char c : t.toCharArray()) { need[c]; } int required 0; for (int i 0; i 128; i) { if (need[i] 0) { required; } } int[] window new int[128]; int matched 0; int left 0; int minLen Integer.MAX_VALUE; int start 0; for (int right 0; right s.length(); right) { char c s.charAt(right); window[c]; if (need[c] 0 window[c] need[c]) { matched; } while (matched required) { int curLen right - left 1; if (curLen minLen) { minLen curLen; start left; } char leftChar s.charAt(left); window[leftChar]--; if (need[leftChar] 0 window[leftChar] need[leftChar]) { matched--; } left; } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }4.3 复杂度计算时间复杂度right指针遍历了整个s一次O(n)left指针在整个过程中最多也只会移动n次O(n)所以总的是 O(n)。哈希表或数组的读写操作是 O(1)。整体时间复杂度为O(n)。空间复杂度如果使用int[128]数组空间为 O(1)如果使用哈希表存储t的字符计数空间为 O(m)其中m是t的长度。由于字符集是固定的英文字母我通常说空间复杂度是 O(1)如果只考虑字符集大小。有一个细节值得提一下计算required的方式。在Python版本里我用len(set(t))在Java版本里遍历need数组统计大于0的个数。两种方式都能得到t中不同字符的种类数。这个值就是matched的目标值。如果省略required直接用matched len(t)判断那是错误的因为t中重复字符会导致重复计数。4.4 用示例跑一遍完整流程用官方示例s ADOBECODEBANCt ABC来手动走一遍初始化need {A:1, B:1, C:1}required 3matched 0left 0min_len inf。right 0c A窗口{A:1}window[A] need[A]matched 1。matched ! required不收缩。right 1c D窗口{A:1, D:1}need[D] 0matched不变。不收缩。right 2c O窗口{A:1, D:1, O:1}matched不变。不收缩。right 3c B窗口{A:1, D:1, O:1, B:1}window[B] need[B]matched 2。不收缩。right 4c Ematched不变。不收缩。right 5c C窗口{A:1, B:1, C:1, D:1, O:1, E:1}window[C] need[C]matched 3。此时窗口覆盖t记录ADOBEC长度6start 0min_len 6。收缩左指针left 0left_char A移出后window[A] 0而need[A] 1window[A] need[A]matched 2left 1。窗口不再覆盖停止收缩。right 6c Omatched不变。不收缩。right 7c Dmatched不变。不收缩。right 8c Ematched不变。不收缩。right 9c B窗口window[B]从1变成2但need[B] 1window[B] need[B]matched不变因为B早就达标了。不收缩。right 10c A窗口window[A]从0变成1window[A] need[A]matched 3。窗口又覆盖了。当前窗口是s[1..10] DOBECODEBA长度10不更新最短长度。收缩左指针left 1left_char D移出后window[D] 1need[D] 0不满足window[D] need[D]matched不变left 2。left 2left_char Owindow[O]--不满足need[O] 0matched不变left 3。left 3left_char Bwindow[B]从2变成1但需要判断的是窗口是否仍然覆盖。此时window[B] 1 need[B]matched不变left 4。left 4left_char E同理matched不变left 5。left 5left_char Cwindow[C]从1变成0window[C] need[C]matched 2left 6。窗口不再覆盖停止收缩。在这个过程中窗口s[3..10] BECODEBA长度8没有更新s[5..10] CODEBA长度6等于当前min_len 6也没有更新。注意这里s[5..10]恰好也覆盖t长度同样是6。right 11c Nmatched不变。不收缩。right 12c C窗口window[C]从0变成1window[C] need[C]matched 3。窗口覆盖当前窗口是s[6..12] ODEBANC长度7不更新最短长度。收缩左指针left 6left_char O移出后matched不变left 7。left 7left_char Dmatched不变left 8。left 8left_char Ematched不变left 9。left 9left_char Bwindow[B]从1变成0window[B] need[B]matched 2left 10。窗口不再覆盖停止收缩。这里窗口在收缩到s[9..12] BANC时长度4比min_len 6短所以min_len 4start 9。right遍历结束返回s[9:94]即BANC。结果正确。手动跑完这一遍基本就能理解两个指针在交替移动时是怎么配合的。关键点在于每次matched变成required时窗口一定覆盖t此时立即收缩左边界并记录最小长度。5. 实测中的陷阱与调优记录超时、边界、错误答案全梳理理论和代码都给出去了但直接交到LeetCode上可能会碰几个实际问题。我把实测中遇到的坑和调优过程整理一下这些是常规题解里很少提到的但对真正写对代码非常重要。5.1 Python版本超时为什么看起来正确的代码跑不过很多人第一次写这题用的Python版本是这样的from collections import Counter def minWindow(s: str, t: str) - str: need Counter(t) window Counter() left 0 res min_len float(inf) for right in range(len(s)): window[s[right]] 1 while all(window.get(ch, 0) need[ch] for ch in need): if right - left 1 min_len: min_len right - left 1 res s[left:right1] window[s[left]] - 1 if window[s[left]] 0: del window[s[left]] left 1 return res这段代码逻辑上完全正确但用all(... for ch in need)做覆盖判断每次收缩都需要遍历t中所有不同字符。如果t有100个不同字符窗口每次收缩都要做100次比较这个常数在某些测试用例里会让代码超时。LeetCode的Python判题环境对于这种理论上O(n)常数巨大的代码是非常不友好的。解决办法就是前面写的matched变量把遍历t判断是否覆盖变成维护一个整数变量。这是从能过样例到稳定AC的关键优化。顺带一提del window[s[left]]这个操作在Python里是O(1)但频繁增删键值对会有一定开销。用定长数组[0] * 128替代Counter性能会更好代码也更简洁。5.2 边界条件清单这些用例一定要自己先测一遍写完代码后我建议至少把这几个边界用例跑一遍s , t A - s A, t - s A, t A - A s A, t B - s AA, t AA - AA s AB, t AA - 因为只有一个A s ADOBECODEBANC, t ABBC - BANC注意B要两个 s abc, t cba - abc顺序无关 s aaaaaaaaaa, t aa - aa答案是第一个合法的任意最短皆可t为空字符串时按题目约定应该返回空串。这个情况有些实现会因为required 0而直接返回整个s需要在开头就拦截。还有一种边界情况容易被忽略t中字符种类很少但某些字符需求量很大。比如s很长t AAAA。这种用例下matched的更新逻辑就特别关键只有window[A]从3变成4那一瞬间matched才加1之后即使A继续增加matched也不会变。如果代码在window[A] need[A]时无条件matched就会导致matched超过required逻辑崩溃。5.3 常见错误代码模式与修复对照根据我在技术社区里看到的提问和讨论这题最常见的错误代码集中在三个地方错误一用window[ch] need[ch]判定matchedif need[ch] 0 and window[ch] need[ch]: matched 1这样会导致matched在字符已经达标后继续增加最终matched会大于required进入while循环后也永远不会退出因为matched只会更大不会变回required。正确写法是只在window[ch] need[ch]时matched。错误二收缩时先移动left再更新window计数left_char s[left] left 1 window[left_char] - 1 # 判断 matched 是否减1这会导致left_char取的是移动前还是移动后的字符搞混逻辑顺序反了。先移left再取s[left]实际上取到的是窗口内第二个字符而第一个字符并没有被移出窗口计数出现错乱。正确顺序是先取left_char s[left]再window[left_char]--最后left 1。错误三把left移到right的位置才停有些写法在收缩时不判断窗口是否仍然覆盖t而是无脑把left一直移到right最后记录一个长度为1的窗口。这显然是错的。收缩的唯一条件是移动后窗口仍然覆盖t一旦matched required就必须停下。5.4 用随机测试验证实现的正确性如果手边用例测完还是不放心可以写一个随机测试脚本把小规模输入的正确结果和暴力法结果做对比import random from collections import Counter def brute_force(s: str, t: str) - str: n len(s) need Counter(t) for length in range(len(t), n 1): for i in range(n - length 1): sub s[i:ilength] window Counter(sub) if all(window[ch] need[ch] for ch in need): return sub return # 随机测试 for _ in range(10000): s .join(random.choice(ABC) for _ in range(random.randint(1, 8))) t .join(random.choice(ABC) for _ in range(random.randint(1, 4))) expected brute_force(s, t) actual minWindow(s, t) if expected ! actual: print(Mismatch!, s, t, expected, actual) break else: print(All tests passed!)这个脚本我建议你在本地跑一遍它能帮你发现一些你根本想象不到的反例。我自己在写这类题时只要不是特别急都会跑一轮随机测试再提交这比反复靠LeetCode的测试点反馈要快得多。6. 从76题延伸出去的通用模式一道题吃透一类滑动窗口LeetCode 76不只是一道题它代表的是一类求满足条件的最短/最长子串的题目。如果你能把这道题的思路彻底想明白很多看似不同的题目都能直接用同一个框架套进去。6.1 变种题对照同一套思路的不同包装先看几个和76题高度相关的变种题题目问题描述与76题的差异解法要点LeetCode 3 无重复字符的最长子串找最长不含重复字符的子串约束是无重复不是覆盖用一个计数器或Set收缩时遇到重复就缩LeetCode 209 长度最小的子数组找和 ≥ target 的最短连续子数组约束是数值和不是字符覆盖维护区间和和满足条件就收缩LeetCode 424 替换后的最长重复字符最多替换k次后找最长重复字符子串约束是最多出现k个其他字符维护窗口内最大字符频率LeetCode 567 字符串的排列找s2中是否包含s1的排列窗口长度固定为len(s1)且必须刚好覆盖固定窗口大小的滑动窗口LeetCode 438 找到字符串中所有字母异位词找s中所有p的异位词起始索引窗口长度固定覆盖判断和76一样固定窗口 字符计数比对从这个表能看出滑动窗口题的共性就是维护一个窗口通过左右指针移动控制窗口内容在窗口满足某个条件时记录答案或调整窗口。区别只在于条件的具体形式。76题的matched变量本质上就是把复杂的覆盖条件变成一个整数比较这个思路在424题、567题里也能复用。6.2 面试中的延伸追问这题还能怎么考我记得有一次模拟面试中面试官在我讲完76题的正解后追问了三个问题这里原样分享给你作为自查追问一如果t中有重复字符你的required会不会算错正确的required是t中不同字符的数量不是t的长度。matched也是按字符种类统计的。所以required要用len(set(t))而不是len(t)。如果这里用错t AABC时required会是4而matched最大只有3程序会一直找不到覆盖窗口。追问二如果s和t都很大但字符集很小比如只有a和b有没有更快的做法这里可以提一下字符集固定的优势need数组长度固定访问是O(1)。如果字符集极小甚至可以进一步用位运算优化到更小的常数。但这个优化通常不需要在面试中展开能说清楚数组比哈希表更快因为避免了哈希计算和可能的冲突就足够了。追问三如果要求返回所有最短覆盖子串而不是任意一个怎么改思路是在记录最短长度时如果出现了同样长度的子串就把起始位置也记录下来。最后根据所有起始位置一次性截取所有长度为min_len的子串。这个改动对核心算法没有影响只是答案存储方式变了。6.3 建模与迁移怎么把新题快速归类到滑动窗口当你遇到一道新的子串/子数组题可以用下面这几个问题快速判断是否适用滑动窗口求的是最长还是最短通常满足条件的最短子串适合右指针尽量扩展后用左指针收缩满足条件的最长子串适合在条件被破坏时收缩。条件是覆盖/包含/总和/频率这种可以用计数或前缀和快速判断的吗如果条件本身需要遍历窗口才能确定那滑动窗口的优势就不存在了。窗口长度的约束是固定的还是可变的固定长度时左指针每次和右指针同步移动逻辑更简单可变长度时需要通过条件判断是否收缩。数据是正数还是可能有负数如果是子数组求和且数组中可能有负数那么滑动窗口就不再适用因为右指针扩展不一定让窗口和变大这时要考虑前缀和哈希表或单调队列。LeetCode 76属于可变窗口 覆盖条件型是最常见也最难的一种。但如果能把这道题的代码结构和matched变量的维护想明白不可变窗口 覆盖条件比如567题基本就是砍掉收缩逻辑的简化版可变窗口 最值条件比如3题就是把覆盖判断换成重复判断。本质上你学到的不是一个解法而是一个状态维护的心智模型。5. LeetCode 76这道题在实际中的价值在刷题社区里这道题被归为Hot 100里的常客也是面试中字符串题目的高优先级题。它的价值不在于背下这段代码而在于它强迫你理解滑动窗口的状态维护。如果你只记住了代码但说不清matched为什么这么维护下一道换皮的题你还是不会。相反如果你把收缩时机、达标判定、状态回滚这三件事的关系搞清楚了那不光76题解决了整个滑动窗口类别里的很多题都能顺手搞定。从另一个角度看这道题也让我想起很多工程场景里的真实需求在日志流里找覆盖所有关键词的最短片段、在生物信息学里找包含所有指定碱基序列的最短片段、在文本处理里找包含全部关键字的最短摘要……这些场景的核心逻辑和LeetCode 76的滑动窗口思路高度一致。6. 个人实操总结踩过坑之后的三个最有效建议聊完了原理、代码和延伸最后说说我实际刷这道题过程中的几个体会希望能帮你少走弯路。第一如果第一次做别急着看题解。先手推一遍官方示例的完整过程自己尝试定义matched的更新规则。等你真正卡在怎么判断覆盖这一步卡得头疼时再回来看我上面写的那段matched维护逻辑印象会深得多。第二代码写完先跑我列出的边界用例再跑一轮随机测试最后才交LeetCode。这个流程看着繁琐但这个排查习惯能帮你建立边界条件敏感性。很多面试里翻车的人不是不会滑动窗口而是栽在t 或s比t短这些空串和长度问题上。第三把这题和其他滑动窗口变种题放在一起对比着刷。只刷一道76题你可能只是会了这道题把3题、209题、424题、567题一起刷你才会真正总结出可变窗口条件收缩和固定窗口计数比较的区别以及面对新题时怎么快速分类。这比盲目刷几十道同类型题效率高得多。最后再补充一个小技巧如果不想自己搭测试环境可以直接在LeetCode的题解区找到一个名为滑动窗口通用模板的思路用那个模板套各种变种题也是一条捷径。但模板始终是别人的自己亲手跑一遍76题的调试过程那种原来如此的体会才是最值钱的。
滑动窗口解LeetCode 76：最短覆盖子串的完整思路与实现
前阵子有个朋友去面试被问了一道字符串里找最短覆盖子串的题回来跟我说Minimum Window Substring这题看着并不难但一上手就发现窗口该什么时候缩、怎么判断已经覆盖了全是坑。我跟他聊完发现很多人都是卡在滑动窗口这个思路的细节落实上——知道要用双指针但写出来的代码要么超时要么边界错。这题是LeetCode 76也是LeetCode 100 hot里的常客刷题指南里基本绕不开。这篇就用完整的思路拆解、代码实现和实测教训把这道题彻底讲透。题目本身的描述很简洁给你一个字符串s、一个字符串t要在s里面找出包含t全部字符的最短子串。注意是包含t的全部字符不是包含t这个子串。也就是说t里的字符可以在s的子串里以任意顺序出现而且如果t里有重复字符子串里也要有对应数量的重复字符才算覆盖。如果你已经会用双指针写无重复字符的最长子串这类题这题看起来只是换了个方向收缩但实际写起来会发现完全不是一回事。这篇文章我会从题目约束开始讲到为什么滑动窗口是正解再到完整的可运行代码和踩坑记录最后延伸到这类题目的通用套路争取让不同基础的人都能看明白。1. 题目到底在问什么约束条件决定了解法方向很多人看到这道题第一反应是用哈希表统计t然后遍历所有子串这思路没错但完全没考虑复杂度。要理解为什么这题必须用滑动窗口而不是别的办法得先把题目的约束条件看透。1.1 题面、示例与最容易被忽略的覆盖定义先看题面。给定一个字符串s一个字符串t返回s中涵盖t所有字符的最小子串。如果s中不存在这样的子串返回空字符串。官方给的示例是输入: s ADOBECODEBANC, t ABC 输出: BANC这个例子里最短的覆盖子串是BANC长度为4。注意ADOBEC也覆盖了ABC但长度是6比BANC长所以不是答案。涵盖t所有字符到底是什么意思这里有三个隐藏规则顺序无关子串里的字符不需要和t中的顺序一致。比如t ABCs BAC的任意包含这三个字符的子串都算覆盖。重复计数t中的重复字符在子串中也必须出现足够的次数。比如t AABC子串必须至少包含两个A、一个B、一个C缺一个A都不算覆盖。额外字符允许子串可以包含t中没有的字符这些字符不影响覆盖判定。比如s ADOBECODEBANC中BANC里的N不在t中但子串依然覆盖。这三条规则就是整个题目的核心语义。很多错误写法都是因为忽略了第二条——只在t中的字符计数上做了判断但在窗口收缩时没有正确维护重复字符的计数。1.2 字符集范围一个决定实现方式的关键细节题目对字符范围有明确约束s和t由英文字母组成但注意题目的标准表述是英文字母大小写都有。这是个影响实现方式的细节。如果只包含小写字母那用一个长度为26的数组来计数就行非常轻松。但如果大小写都有就是52个字符。更通用的做法是假设任意ASCII字符128个甚至Unicode字符。LeetCode的测试用例里这两种情况都可能出现所以写代码时直接把计数结构做成能处理任意字符会比较稳。我见过不少人在这里翻车用一个长度为26的数组结果遇到大写字母就直接越界或者认为只有小写字母导致某些隐藏测试用例失败。实际上LeetCode这道题的输入范围是英文字母但s和t都有可能包含大写和小写稳妥起见计数数组开到128覆盖所有ASCII字符是最省心的做法或者直接用HashMap/Counter。字符集范围会影响时间复杂度的常数但不影响算法本身的量级。比如用数组计数访问是O(1)用哈希表计数访问平均也是O(1)。但数组的方式常数更小运行更快这在LeetCode的耗时排名上是有直观体现的。1.3 暴力解的时间账单为什么必须放弃假设我们先不考虑效率用最直观的暴力法枚举s的所有子串对每个子串判断是否覆盖t。枚举所有子串的数量是O(n^2)每个子串长度为O(n)统计子串中每个字符出现次数需要O(n)时间和t的计数比较又需要O(m)时间m是t的长度。所以总复杂度是O(n^3)级别。如果s的长度是10万LeetCode的测试用例确实可以达到这个量级n^3的计算量是天文数字根本跑不完。这就是为什么暴力法在算法题里只能作为理解题意的辅助手段不能作为正式解法。从这个复杂度账单能看出优化方向上只有两条路要么减少枚举子串的数量要么降低判断覆盖的时间。滑动窗口同时解决了这两个问题窗口移动的总次数是O(n)覆盖判断通过维护一个计数器变成O(1)。后面会详细展开。2. 为什么滑动窗口是这题的正解从暴力法的时间账单说起滑动窗口不是一个高深莫测的算法它的本质是用两个指针维护一个区间根据条件动态调整区间起点和终点。但要搞清楚为什么它适合这题得先从暴力法的劣势开始分析。2.1 暴力法的实际成本重复计算是最大的浪费暴力法的关键浪费在于当我们枚举子串s[i..j]和s[i..j1]时后者比前者只多了一个字符但我们依然从头开始统计后者的所有字符出现次数。这太浪费了。举个例子s ADOBECODEBANC枚举子串ADOBE和ADOBEC后者就是前者加了一个C。如果重新统计ADOBEC里每个字符的次数那A、D、O、B、E这五个字符的计数等于白算了一遍。增量更新的思想在这里非常自然每次只更新新加入的那个字符的计数而不是重新统计整个子串。这是从暴力法走向滑动窗口的第一步认知。2.2 滑动窗口的本质两个指针维护区间增量更新状态滑动窗口的框架是右指针right不断向右扩展扩大窗口范围当窗口已经覆盖了t中的所有字符时尝试移动左指针left向右收缩尽量缩短窗口长度一旦收缩到不满足覆盖条件就停下来继续移动右指针。整个过程像一条毛毛虫在绳子上爬行左边界和右边界交替前进。这样做的核心收益有两方面每个字符最多被右指针访问一次、被左指针访问一次。总移动次数是O(n)而不是O(n^2)。通过维护一个当前窗口中有多少个字符已经满足了t的要求的计数器判断窗口是否覆盖t的时间从O(m)降到了O(1)。关于第二点很多人写这题时的困惑是每次判断窗口是否覆盖t难道不需要重新遍历t的所有字符检查它们在窗口中的计数是否达标吗如果这样做那又变回O(n^2)了。正确做法是维护一个变量matched有的叫formed记录当前窗口内已经达到t所需数量的字符种类数。当matched len(t的字符种类数)时说明窗口已经覆盖了t。这个变量的更新在每次右指针扩窗和左指针收缩时同步进行都是O(1)操作。2.3 这道题和无重复字符最长子串的本质区别很多人之前刷过LeetCode 3无重复字符的最长子串那道题也是滑动窗口但两道题在窗口收缩的逻辑上有个重要区别如果不区分清楚做76题时会踩坑。在LeetCode 3里窗口内不能有重复字符所以一旦右指针指向的字符已经在窗口内就必须收缩左指针直到该字符离开窗口。那道题只有一个约束条件且约束是硬性的——窗口内不能有重复字符。而在76题里窗口的覆盖条件是软性的——窗口内允许有任意数量的额外字符只要t中的字符都出现足够次数就行。所以收缩左指针的时机不是右指针字符重复了而是左指针指向的字符在移出窗口后窗口仍然保持对t的覆盖。这个判断需要用到该字符在t中是否有要求以及移出后数量是否仍然达标。我见过不少初学者把这两道题的收缩逻辑混在一起结果就是窗口缩过头了或者不知道怎么判断还能不能继续缩。后面写代码时我会用具体的例子说明这个区别。3. 写代码前的三个关键决策计数、判定与收缩时机确定用滑动窗口之后接下来就是几个关键的实现决策。这些决策直接决定代码的简洁度和运行效率。我建议你在写代码之前先把这三个问题想清楚否则很容易写出逻辑绕来绕去还不对的版本。3.1 计数结构用数组还是哈希表统计t中每个字符的需求量主流做法有两种方案实现时间复杂度空间复杂度优点缺点数组计数int[] need new int[128]O(1) 更新O(128) O(1)访问快常数小得知道字符范围字符集很大时浪费空间哈希表计数MapCharacter, IntegerO(1) 平均O(m)灵活适合任意字符集常数较大代码相对繁琐我个人在LeetCode 76的题解里更喜欢用数组因为题目输入已经限定为英文字母大小写数组开到128完全够用。假如你是为了应对面试可以先问面试官字符集范围如果对方说任意ASCII字符数组方案依然是安全的。如果扩大到Unicode那哈希表更合适。用数组时有个小技巧数组的下标直接用字符的ASCII码比如need[A]。虽然A的数值是65但Java和Python这种语言都允许用字符作为数组下标Python用字典时无所谓Java的数组下标必须是int但char会自动转成int。这样写的好处是代码可读性高不用手动做c - A的换算。3.2 窗口是否覆盖的判断如何做到O(1)窗口覆盖t的判断最笨的方法是每次都用t的字符集遍历一遍检查窗口内每个字符的计数是否都大于等于需求量。但这样每移动一次指针就要O(m)时间总体会变成O(n*m)虽然比O(n^2)好一些但不够优雅而且在m很大时也可能超时。标准做法是维护一个变量比如叫matched或covered表示当前窗口内已经满足需求的字符种类数。它和t中的字符种类数比较。当两者相等时窗口就覆盖了t。具体维护逻辑是这样的右指针right指向的字符c进入窗口window[c]加1。如果window[c] need[c]说明字符c在窗口里的数量已经达标matched加1。左指针left指向的字符c移出窗口window[c]减1。如果window[c] need[c]注意是减之前等于need[c]减之后小于说明字符c的数量不再达标matched减1。这里有个容易绕晕的点为什么右指针扩展时是等于才matched左指针收缩时是小于才matched--因为matched记录的是达标的字符种类数每种字符只有达到需求量和没达到需求量两个状态。当window[c]从need[c] - 1变成need[c]就是从不达标变成达标的瞬间这时才需要更新matched。反过来当window[c]从need[c]变成need[c] - 1就是达标变成不达标的瞬间这时才matched--。很多错误的代码就是在这里多写或少写了判断条件导致matched计数不准最后整个逻辑错乱。3.3 收缩左指针时的状态回滚细节当窗口覆盖t时我们需要记录当前窗口长度和起始位置然后尝试收缩左指针。收缩时有一个经典错误直接移动left但忘记同步更新window数组和matched变量。这会导致后续判断全部出错。正确的收缩流程是记录当前窗口长度len right - left 1如果比已记录的最短长度还要短更新最短长度和起始位置。将left指向的字符c从window中移除window[c]--。如果移除后window[c] need[c]说明字符c不再达标matched--。将left右移一位。重复上述过程直到matched required即窗口不再覆盖t。这里还有一个细节很多人没注意如果left指向的字符c根本不在t中那么need[c]为0无论window[c]是多少移除后都不会出现window[c] need[c]所以matched不会变化窗口可以继续收缩。这说明额外字符不会阻塞收缩过程和前面讲的额外字符允许语义一致。状态回滚看起来简单但在写代码时很容易漏掉第3步。我当时第一次写这题时就是漏了这步导致收缩一次后matched没有及时减1窗口明明已经不覆盖了程序还以为覆盖结果答案错误。后来我专门把这三步流程写在注释里才彻底理清。4. 完整实现与逐段拆解两个指针滑动出最优解下面给出一个经过实测的Python实现以及对应的Java版本。Python版本比较好读适合理解算法逻辑Java版本适合提交到LeetCode时追求更快的运行速度。4.1 Python参考实现def minWindow(s: str, t: str) - str: if len(s) len(t): return # 统计 t 中每个字符的需求量 need [0] * 128 for ch in t: need[ord(ch)] 1 required len(set(t)) # t 中有多少种不同字符 window [0] * 128 # 当前窗口内每个字符的出现次数 matched 0 # 当前窗口中已经达标达到需求量的字符种类数 left 0 min_len float(inf) start 0 # 右指针向右扩展窗口 for right in range(len(s)): c s[right] window[ord(c)] 1 # 如果 c 在 t 中且窗口内 c 的数量刚刚达到需求量则 matched 加 1 if need[ord(c)] 0 and window[ord(c)] need[ord(c)]: matched 1 # 当窗口覆盖 t 时尝试收缩左边界 while matched required: cur_len right - left 1 if cur_len min_len: min_len cur_len start left # 左指针右移前先把 left 指向的字符移出窗口 left_char s[left] window[ord(left_char)] - 1 if need[ord(left_char)] 0 and window[ord(left_char)] need[ord(left_char)]: matched - 1 left 1 if min_len float(inf): return return s[start:start min_len]4.2 Java参考实现class Solution { public String minWindow(String s, String t) { if (s.length() t.length()) { return ; } int[] need new int[128]; for (char c : t.toCharArray()) { need[c]; } int required 0; for (int i 0; i 128; i) { if (need[i] 0) { required; } } int[] window new int[128]; int matched 0; int left 0; int minLen Integer.MAX_VALUE; int start 0; for (int right 0; right s.length(); right) { char c s.charAt(right); window[c]; if (need[c] 0 window[c] need[c]) { matched; } while (matched required) { int curLen right - left 1; if (curLen minLen) { minLen curLen; start left; } char leftChar s.charAt(left); window[leftChar]--; if (need[leftChar] 0 window[leftChar] need[leftChar]) { matched--; } left; } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }4.3 复杂度计算时间复杂度right指针遍历了整个s一次O(n)left指针在整个过程中最多也只会移动n次O(n)所以总的是 O(n)。哈希表或数组的读写操作是 O(1)。整体时间复杂度为O(n)。空间复杂度如果使用int[128]数组空间为 O(1)如果使用哈希表存储t的字符计数空间为 O(m)其中m是t的长度。由于字符集是固定的英文字母我通常说空间复杂度是 O(1)如果只考虑字符集大小。有一个细节值得提一下计算required的方式。在Python版本里我用len(set(t))在Java版本里遍历need数组统计大于0的个数。两种方式都能得到t中不同字符的种类数。这个值就是matched的目标值。如果省略required直接用matched len(t)判断那是错误的因为t中重复字符会导致重复计数。4.4 用示例跑一遍完整流程用官方示例s ADOBECODEBANCt ABC来手动走一遍初始化need {A:1, B:1, C:1}required 3matched 0left 0min_len inf。right 0c A窗口{A:1}window[A] need[A]matched 1。matched ! required不收缩。right 1c D窗口{A:1, D:1}need[D] 0matched不变。不收缩。right 2c O窗口{A:1, D:1, O:1}matched不变。不收缩。right 3c B窗口{A:1, D:1, O:1, B:1}window[B] need[B]matched 2。不收缩。right 4c Ematched不变。不收缩。right 5c C窗口{A:1, B:1, C:1, D:1, O:1, E:1}window[C] need[C]matched 3。此时窗口覆盖t记录ADOBEC长度6start 0min_len 6。收缩左指针left 0left_char A移出后window[A] 0而need[A] 1window[A] need[A]matched 2left 1。窗口不再覆盖停止收缩。right 6c Omatched不变。不收缩。right 7c Dmatched不变。不收缩。right 8c Ematched不变。不收缩。right 9c B窗口window[B]从1变成2但need[B] 1window[B] need[B]matched不变因为B早就达标了。不收缩。right 10c A窗口window[A]从0变成1window[A] need[A]matched 3。窗口又覆盖了。当前窗口是s[1..10] DOBECODEBA长度10不更新最短长度。收缩左指针left 1left_char D移出后window[D] 1need[D] 0不满足window[D] need[D]matched不变left 2。left 2left_char Owindow[O]--不满足need[O] 0matched不变left 3。left 3left_char Bwindow[B]从2变成1但需要判断的是窗口是否仍然覆盖。此时window[B] 1 need[B]matched不变left 4。left 4left_char E同理matched不变left 5。left 5left_char Cwindow[C]从1变成0window[C] need[C]matched 2left 6。窗口不再覆盖停止收缩。在这个过程中窗口s[3..10] BECODEBA长度8没有更新s[5..10] CODEBA长度6等于当前min_len 6也没有更新。注意这里s[5..10]恰好也覆盖t长度同样是6。right 11c Nmatched不变。不收缩。right 12c C窗口window[C]从0变成1window[C] need[C]matched 3。窗口覆盖当前窗口是s[6..12] ODEBANC长度7不更新最短长度。收缩左指针left 6left_char O移出后matched不变left 7。left 7left_char Dmatched不变left 8。left 8left_char Ematched不变left 9。left 9left_char Bwindow[B]从1变成0window[B] need[B]matched 2left 10。窗口不再覆盖停止收缩。这里窗口在收缩到s[9..12] BANC时长度4比min_len 6短所以min_len 4start 9。right遍历结束返回s[9:94]即BANC。结果正确。手动跑完这一遍基本就能理解两个指针在交替移动时是怎么配合的。关键点在于每次matched变成required时窗口一定覆盖t此时立即收缩左边界并记录最小长度。5. 实测中的陷阱与调优记录超时、边界、错误答案全梳理理论和代码都给出去了但直接交到LeetCode上可能会碰几个实际问题。我把实测中遇到的坑和调优过程整理一下这些是常规题解里很少提到的但对真正写对代码非常重要。5.1 Python版本超时为什么看起来正确的代码跑不过很多人第一次写这题用的Python版本是这样的from collections import Counter def minWindow(s: str, t: str) - str: need Counter(t) window Counter() left 0 res min_len float(inf) for right in range(len(s)): window[s[right]] 1 while all(window.get(ch, 0) need[ch] for ch in need): if right - left 1 min_len: min_len right - left 1 res s[left:right1] window[s[left]] - 1 if window[s[left]] 0: del window[s[left]] left 1 return res这段代码逻辑上完全正确但用all(... for ch in need)做覆盖判断每次收缩都需要遍历t中所有不同字符。如果t有100个不同字符窗口每次收缩都要做100次比较这个常数在某些测试用例里会让代码超时。LeetCode的Python判题环境对于这种理论上O(n)常数巨大的代码是非常不友好的。解决办法就是前面写的matched变量把遍历t判断是否覆盖变成维护一个整数变量。这是从能过样例到稳定AC的关键优化。顺带一提del window[s[left]]这个操作在Python里是O(1)但频繁增删键值对会有一定开销。用定长数组[0] * 128替代Counter性能会更好代码也更简洁。5.2 边界条件清单这些用例一定要自己先测一遍写完代码后我建议至少把这几个边界用例跑一遍s , t A - s A, t - s A, t A - A s A, t B - s AA, t AA - AA s AB, t AA - 因为只有一个A s ADOBECODEBANC, t ABBC - BANC注意B要两个 s abc, t cba - abc顺序无关 s aaaaaaaaaa, t aa - aa答案是第一个合法的任意最短皆可t为空字符串时按题目约定应该返回空串。这个情况有些实现会因为required 0而直接返回整个s需要在开头就拦截。还有一种边界情况容易被忽略t中字符种类很少但某些字符需求量很大。比如s很长t AAAA。这种用例下matched的更新逻辑就特别关键只有window[A]从3变成4那一瞬间matched才加1之后即使A继续增加matched也不会变。如果代码在window[A] need[A]时无条件matched就会导致matched超过required逻辑崩溃。5.3 常见错误代码模式与修复对照根据我在技术社区里看到的提问和讨论这题最常见的错误代码集中在三个地方错误一用window[ch] need[ch]判定matchedif need[ch] 0 and window[ch] need[ch]: matched 1这样会导致matched在字符已经达标后继续增加最终matched会大于required进入while循环后也永远不会退出因为matched只会更大不会变回required。正确写法是只在window[ch] need[ch]时matched。错误二收缩时先移动left再更新window计数left_char s[left] left 1 window[left_char] - 1 # 判断 matched 是否减1这会导致left_char取的是移动前还是移动后的字符搞混逻辑顺序反了。先移left再取s[left]实际上取到的是窗口内第二个字符而第一个字符并没有被移出窗口计数出现错乱。正确顺序是先取left_char s[left]再window[left_char]--最后left 1。错误三把left移到right的位置才停有些写法在收缩时不判断窗口是否仍然覆盖t而是无脑把left一直移到right最后记录一个长度为1的窗口。这显然是错的。收缩的唯一条件是移动后窗口仍然覆盖t一旦matched required就必须停下。5.4 用随机测试验证实现的正确性如果手边用例测完还是不放心可以写一个随机测试脚本把小规模输入的正确结果和暴力法结果做对比import random from collections import Counter def brute_force(s: str, t: str) - str: n len(s) need Counter(t) for length in range(len(t), n 1): for i in range(n - length 1): sub s[i:ilength] window Counter(sub) if all(window[ch] need[ch] for ch in need): return sub return # 随机测试 for _ in range(10000): s .join(random.choice(ABC) for _ in range(random.randint(1, 8))) t .join(random.choice(ABC) for _ in range(random.randint(1, 4))) expected brute_force(s, t) actual minWindow(s, t) if expected ! actual: print(Mismatch!, s, t, expected, actual) break else: print(All tests passed!)这个脚本我建议你在本地跑一遍它能帮你发现一些你根本想象不到的反例。我自己在写这类题时只要不是特别急都会跑一轮随机测试再提交这比反复靠LeetCode的测试点反馈要快得多。6. 从76题延伸出去的通用模式一道题吃透一类滑动窗口LeetCode 76不只是一道题它代表的是一类求满足条件的最短/最长子串的题目。如果你能把这道题的思路彻底想明白很多看似不同的题目都能直接用同一个框架套进去。6.1 变种题对照同一套思路的不同包装先看几个和76题高度相关的变种题题目问题描述与76题的差异解法要点LeetCode 3 无重复字符的最长子串找最长不含重复字符的子串约束是无重复不是覆盖用一个计数器或Set收缩时遇到重复就缩LeetCode 209 长度最小的子数组找和 ≥ target 的最短连续子数组约束是数值和不是字符覆盖维护区间和和满足条件就收缩LeetCode 424 替换后的最长重复字符最多替换k次后找最长重复字符子串约束是最多出现k个其他字符维护窗口内最大字符频率LeetCode 567 字符串的排列找s2中是否包含s1的排列窗口长度固定为len(s1)且必须刚好覆盖固定窗口大小的滑动窗口LeetCode 438 找到字符串中所有字母异位词找s中所有p的异位词起始索引窗口长度固定覆盖判断和76一样固定窗口 字符计数比对从这个表能看出滑动窗口题的共性就是维护一个窗口通过左右指针移动控制窗口内容在窗口满足某个条件时记录答案或调整窗口。区别只在于条件的具体形式。76题的matched变量本质上就是把复杂的覆盖条件变成一个整数比较这个思路在424题、567题里也能复用。6.2 面试中的延伸追问这题还能怎么考我记得有一次模拟面试中面试官在我讲完76题的正解后追问了三个问题这里原样分享给你作为自查追问一如果t中有重复字符你的required会不会算错正确的required是t中不同字符的数量不是t的长度。matched也是按字符种类统计的。所以required要用len(set(t))而不是len(t)。如果这里用错t AABC时required会是4而matched最大只有3程序会一直找不到覆盖窗口。追问二如果s和t都很大但字符集很小比如只有a和b有没有更快的做法这里可以提一下字符集固定的优势need数组长度固定访问是O(1)。如果字符集极小甚至可以进一步用位运算优化到更小的常数。但这个优化通常不需要在面试中展开能说清楚数组比哈希表更快因为避免了哈希计算和可能的冲突就足够了。追问三如果要求返回所有最短覆盖子串而不是任意一个怎么改思路是在记录最短长度时如果出现了同样长度的子串就把起始位置也记录下来。最后根据所有起始位置一次性截取所有长度为min_len的子串。这个改动对核心算法没有影响只是答案存储方式变了。6.3 建模与迁移怎么把新题快速归类到滑动窗口当你遇到一道新的子串/子数组题可以用下面这几个问题快速判断是否适用滑动窗口求的是最长还是最短通常满足条件的最短子串适合右指针尽量扩展后用左指针收缩满足条件的最长子串适合在条件被破坏时收缩。条件是覆盖/包含/总和/频率这种可以用计数或前缀和快速判断的吗如果条件本身需要遍历窗口才能确定那滑动窗口的优势就不存在了。窗口长度的约束是固定的还是可变的固定长度时左指针每次和右指针同步移动逻辑更简单可变长度时需要通过条件判断是否收缩。数据是正数还是可能有负数如果是子数组求和且数组中可能有负数那么滑动窗口就不再适用因为右指针扩展不一定让窗口和变大这时要考虑前缀和哈希表或单调队列。LeetCode 76属于可变窗口 覆盖条件型是最常见也最难的一种。但如果能把这道题的代码结构和matched变量的维护想明白不可变窗口 覆盖条件比如567题基本就是砍掉收缩逻辑的简化版可变窗口 最值条件比如3题就是把覆盖判断换成重复判断。本质上你学到的不是一个解法而是一个状态维护的心智模型。5. LeetCode 76这道题在实际中的价值在刷题社区里这道题被归为Hot 100里的常客也是面试中字符串题目的高优先级题。它的价值不在于背下这段代码而在于它强迫你理解滑动窗口的状态维护。如果你只记住了代码但说不清matched为什么这么维护下一道换皮的题你还是不会。相反如果你把收缩时机、达标判定、状态回滚这三件事的关系搞清楚了那不光76题解决了整个滑动窗口类别里的很多题都能顺手搞定。从另一个角度看这道题也让我想起很多工程场景里的真实需求在日志流里找覆盖所有关键词的最短片段、在生物信息学里找包含所有指定碱基序列的最短片段、在文本处理里找包含全部关键字的最短摘要……这些场景的核心逻辑和LeetCode 76的滑动窗口思路高度一致。6. 个人实操总结踩过坑之后的三个最有效建议聊完了原理、代码和延伸最后说说我实际刷这道题过程中的几个体会希望能帮你少走弯路。第一如果第一次做别急着看题解。先手推一遍官方示例的完整过程自己尝试定义matched的更新规则。等你真正卡在怎么判断覆盖这一步卡得头疼时再回来看我上面写的那段matched维护逻辑印象会深得多。第二代码写完先跑我列出的边界用例再跑一轮随机测试最后才交LeetCode。这个流程看着繁琐但这个排查习惯能帮你建立边界条件敏感性。很多面试里翻车的人不是不会滑动窗口而是栽在t 或s比t短这些空串和长度问题上。第三把这题和其他滑动窗口变种题放在一起对比着刷。只刷一道76题你可能只是会了这道题把3题、209题、424题、567题一起刷你才会真正总结出可变窗口条件收缩和固定窗口计数比较的区别以及面对新题时怎么快速分类。这比盲目刷几十道同类型题效率高得多。最后再补充一个小技巧如果不想自己搭测试环境可以直接在LeetCode的题解区找到一个名为滑动窗口通用模板的思路用那个模板套各种变种题也是一条捷径。但模板始终是别人的自己亲手跑一遍76题的调试过程那种原来如此的体会才是最值钱的。
