有一类字符串题面试官一说出来大部分人的第一反应就是枚举给你字符串s和t在s里找出包含t所有字符的最短子串。这就是 LeetCode 第 76 题「最小覆盖子串」通常被标成 Hard但题目本身并不难难的是你愿不愿意从“枚举所有子串”一步步优化到“滑动窗口”。我面试时见过这道题也陪朋友练过很多遍今天这篇就完整拆一下先讲最笨但最好懂的枚举法再讲标准滑动窗口的推导过程、实现细节和边界坑最后聊面试时怎么一步步把思路讲顺。如果你正在准备算法面试或者刷题刷到字符串双指针部分卡住了这篇文章会给你一套能直接复现、能照抄的完整方案。通篇围绕“最小覆盖子串”这一个点讲透不扯虚的。1. 先把题意吃透什么叫做“覆盖”什么叫做“最小”1.1 题面复述与示例推演题目说的是给定两个字符串s和t返回s中涵盖t所有字符的最小子串。如果s里不存在这样的子串返回空字符串。注意“涵盖”是关键词窗口里每个字符出现的次数必须都不少于t里该字符出现的次数。举个例子s ADOBECODEBANCt ABC。肉眼扫一遍能包含A、B、C的子串不少ADOBEC长度 6CODEBA长度 6BANC长度 4ANC不行缺 B。最短的就是BANC。为什么不是更靠前的ADOBEC因为它虽然包含了三个目标字符但长度更长。我们要的“最小”是在所有合法覆盖子串里取长度最小的那个不是找第一个出现的。多个答案长度相同且都合法时返回任意一个即可判题器会接受。另外题目默认大小写敏感a和A是两个完全不同的字符。这一点别看轻了很多人在手写用例时忽略掉等跑起来才发现自己的窗口把大小写混在一起统计了。1.2 一个容易掉进去的坑t 里字符重复怎么办“覆盖”这个词容易让人想到集合但是t里的字符可能会重复。比如t aa那s的窗口里至少要有两个a只有一个a是不能算覆盖的。这是很多初学者写错的地方用set(t)去判断窗口里有没有这些字符直接忽略次数要求。对t aa这种输入window里只要出现一个aset判断就通过了但正确答案应该是一个长度为 2、包含两个a的窗口。所以判断覆盖状态的核心一定基于字符计数而不是简单查一下 HashSet。这也是后面所有方案都离不开计数器的原因。牢牢记住count(window[c]) count(t[c])才是合法覆盖。窗口里可以比t需要的字符多比如t aa窗口aaa是合法覆盖因为a的数量 3 不小于 2。1.3 写代码前先确认边界条件我刷题的习惯是先想边界再写主体。这道题的边界条件主要是这几个s或t为空直接返回空字符串。len(s) len(t)s总长度都不够肯定不可能覆盖返回空字符串。t中所有字符在s里根本凑不齐返回空字符串。s和t长度都为 1且字符相同返回s自身。t长度很短但s很长比如s aaaa...at a任意一个单字符窗口都合法返回哪个都行常见代码会返回最左边那个。把边界在草稿纸上列一遍再动手后面实现起来会稳很多。很多提交在 LeetCode 上 WA不是主逻辑错而是空字符串、找不到这类兜底没做好。2. 枚举法最笨但最能解释清楚的方法2.1 枚举起点固定 i向右找第一个满足的 j第一种最直觉的做法枚举子串的起始下标i然后让j从i向右移动一边移动一边维护窗口里各字符的计数一旦当前窗口已经覆盖了t就停住记录这个窗口的长度再换下一个i。为什么j第一次满足条件就停因为j再往右走窗口只会更长不可能比当前这个更优。所以对固定起点i来说第一个覆盖点就是最优解。代码写出来长这样from collections import Counter def min_window_enum_start(s: str, t: str) - str: if not s or not t or len(s) len(t): return need Counter(t) ans for i in range(len(s)): window {} for j in range(i, len(s)): window[s[j]] window.get(s[j], 0) 1 if all(window.get(ch, 0) need[ch] for ch in need): if ans or (j - i 1) len(ans): ans s[i:j 1] break return ansall(...)每次检查t里所有字符是否都满足数量要求。这个写法正确性一目了然和小白解释“什么叫覆盖”特别好使。但它的代价是每换一个起点i都要重新从i开始累加计数前一个窗口统计过的字符全部浪费掉了。2.2 枚举长度按窗口长度从短到长扫描另一种枚举思路是按窗口长度来。窗口最短不可能短于len(t)最长是len(s)。于是从小到大枚举长度L在每个长度下用窗口左端点i滑过整个s检查所有长度为L的子串只要找到一个合法的就返回因为越短的越早被发现。from collections import Counter def min_window_enum_len(s: str, t: str) - str: if not s or not t or len(s) len(t): return need Counter(t) for L in range(len(t), len(s) 1): for i in range(0, len(s) - L 1): sub s[i:i L] window Counter(sub) if all(window.get(ch, 0) need[ch] for ch in need): return sub return 这段比 2.1 还好理解但每次切sub都生成新字符串底层又是一次 O(L) 的复制。如果s长度是 10^5这个方案基本不可能跑完。不过作为“正确答案的验证器”在随机小规模测试里对照滑动窗口的输出非常有用。2.3 枚举法的复杂度账本切片是隐性炸弹枚举起点的方案最坏要枚举 O(n^2) 个窗口每个窗口做一次覆盖检查。如果t的字符种类数是k检查all(...)就是 O(k)。总复杂度可以粗估为 O(n^2 * k)。这里有个很多人忽略的点切片很贵。如果在循环里面频繁写s[i:j1]每次切片都是 O(len) 的复制会直接把 O(n^2) 拉高到 O(n^3)。所以在枚举代码里我只在找到答案之后才切一次中间只记录下标和长度。这一点对后面优化版本同样适用能不用切片就不用切片。枚举法有没有机会过如果s很短比如几百个字符t也很短那它可以秒过。我自己在本地做随机测试时反而会专门留一份枚举法代码用来和滑动窗口版本对拍确保优化后的代码没有改错逻辑。它作为“思路垫脚石”的价值远大于作为“最终提交方案”的价值。3. 滑动窗口的推导从“重复扫描”到“一把尺子来回量”3.1 观察到问题本质很多计数是重复劳动再看 2.1 的枚举起点法。以s ADOBECODEBANC,t ABC为例起点i 0时窗口扫到ADOBEC才覆盖j 5起点i 1时窗口从D开始重新数又要一直扫到j 10附近才覆盖起点i 2时窗口从O开始又是重新数。但i 1的窗口和i 0的窗口有很大一段是重叠的。i 1的窗口在覆盖前只不过是把i 0窗口的头部字符A去掉再往后补几个新字符而已。既然这样为什么要从零开始重建计数呢这就是滑动窗口的第一层动机复用上一次窗口的统计结果。右指针每前进一格只需要把新字符的计数加 1左指针每前进一格只需要把离开窗口的字符计数减 1。这样每个字符只被加一次、减一次总工作量从 O(n^2) 降到 O(n)。3.2 关键论证为什么左右指针都可以只往右走有了两端的指针之后很多人会担心这样左一下右一下会不会漏掉某些合法窗口答案是不会关键在于一个单调性随着左指针 left 不断右移能够覆盖 t 的右指针 right 的“最短合法位置”不会左移。这句话可以这样理解窗口去掉头部字符后字符总数变少覆盖能力只会下降不会上升。原本窗口覆盖t去掉一个字符后可能就不覆盖了那只能把 right 往右延伸去补字符。所以说right 的移动方向是单调的从前往后扫一遍就足够。这个性质保证了双指针算法的完备性任意一个最优窗口[l, r]当 right 到达r时left 一定已经停在某个不超过l的位置然后 while 循环不断收缩 left经过l的那一刻就一定记录到了[l, r]这个窗口。整个过程中left 和 right 各自至多移动 n 次算法也就不会漏解。3.3 滑动窗口的运作状态机用一句话概括滑动窗口的日常right负责扩张扩张到覆盖为止left负责收缩收缩到刚好不覆盖为止。每次收缩前当前窗口是一个合法覆盖记录它的长度一旦收缩后不再覆盖就停下来让right继续往前走。可以把它看成一个循环往复的过程right不断右移把字符纳入窗口更新计数当窗口已经覆盖t进入收缩阶段在收缩循环里先记录当前窗口再把left右移、更新计数如果收缩后仍然覆盖继续收缩如果不覆盖退出循环right继续右移重复整个过程。每一步都是 O(1) 的计数更新整个算法的代价就是两个指针总共扫过一遍字符串复杂度 O(n)。这就是“枚举所有子串”到“利用单调性只遍历必要窗口”的优化本质。4. 标准滑动窗口实现计数器、missing 值与收缩时机4.1 计数器设计固定数组还是哈希表实现之前先决定怎么存。t里的字符无非 ASCII 范围内的字母和符号LeetCode 原题通常也只给英文字母。最省事的方式是开一个长度为 128 的数组直接把字符转成 ASCII 下标need记录t的需求window记录当前窗口的实际计数为什么是 128ASCII 范围 0~127包含所有常见英文字符直接ord(ch)取下标。如果题目明确只有大写/小写字母可以压缩到 52 长度再映射但没必要128 已经是常数级空间。如果字符集可能很大比如 Unicode数组就不合适了用Counter或defaultdict更稳。判断覆盖状态时如果每次都用all(...)比较两个 Counter复杂度又要乘上字符种类数。更好的办法是维护一个整数状态量常见两种写法写法 Amissing 总数设missing len(t)表示窗口还缺多少个字符。每次右指针纳入字符c时如果window[c] need[c]说明这个字符补上了一个缺口missing - 1。左指针收缩时反向处理。写法 Bformed 种类数设need_size len(need)表示t里有几种字符。当窗口里某种字符的数量从小于need[c]变成刚好等于need[c]时formed 1。当formed need_size时窗口覆盖t。两种写法都可以我下面主要用写法 B因为它和“每种字符是否达标”的语义更贴近不容易在字符数量超过需求时算错账。4.2 formed 计数的精确条件必须是等于不是大于等于写法 B 有个细节极其容易写错。右指针纳入字符c后更新窗口计数的同时判断if window[c] need[c]: formed 1这里必须是不能是。原因是formed只统计“从没达标变成刚好达标”的那一次。假如need[a] 2窗口里a的数量从 2 变成 3 时a本来就达标了不能再让formed加 1否则formed会超过need_size破坏判断逻辑。对应的左指针收缩时窗口计数的更新顺序是先把window[c] - 1然后判断if window[c] need[c]: formed - 1也就是说只有当字符数量从达标变成不达标时formed才减 1。注意要先减计数再判断顺序反了会得到错误结果。4.3 完整可提交的 Python 实现from collections import Counter def minWindow(s: str, t: str) - str: if not s or not t or len(s) len(t): return need Counter(t) window Counter() need_size len(need) formed 0 left 0 min_len float(inf) start 0 for right, char in enumerate(s): window[char] 1 if window[char] need[char]: formed 1 while formed need_size: if right - left 1 min_len: min_len right - left 1 start left left_char s[left] window[left_char] - 1 if window[left_char] need[left_char]: formed - 1 left 1 return if min_len float(inf) else s[start:start min_len]逐个注意点过一遍window里统计了所有出现在s中的字符包括不在t里的字符。这些多余字符是否会干扰formed不会因为need[X] 0window[X]永远不可能等于 0只要它进了窗口就至少是 1所以条件不成立不会误加formed。while循环退出条件必须是formed need_size。只要达标就收缩收缩到不达标才停因为我们要找最短窗口能缩就缩。记录答案的位置在收缩循环体内每缩一步都记录一次这样不会错过“中间某个更短但依然合法”的窗口。找不到时min_len依然是inf最后返回空串。这里不要马虎写成返回None题面要求是空字符串。4.4 C 版本面试中常见的写法如果你面的是 C 岗位或者刷题时习惯用 C下面这份可以直接背class Solution { public: string minWindow(string s, string t) { if (s.empty() || t.empty() || s.size() t.size()) return ; vectorint need(128, 0), window(128, 0); for (char c : t) need[c]; int needSize 0; for (int i 0; i 128; i) { if (need[i] 0) needSize; } int formed 0; int left 0; int minLen INT_MAX; int start 0; for (int right 0; right s.size(); right) { char c s[right]; window[c]; if (window[c] need[c]) formed; while (formed needSize) { if (right - left 1 minLen) { minLen right - left 1; start left; } char leftChar s[left]; window[leftChar]--; if (window[leftChar] need[leftChar]) formed--; left; } } return minLen INT_MAX ? : s.substr(start, minLen); } };和 Python 版逻辑完全一致。C 用数组当计数器比unordered_map快不少因为数组下标访问是 O(1) 且没有哈希开销。这也是面试官比较喜欢看到的写法。5. 三种实现的复杂度与实测谁在什么场景下胜出5.1 复杂度对比表把前面提到的方案放一起对比实现方案核心思路时间复杂度空间复杂度适合场景暴力枚举所有子串双层循环 i, j检查每个子串O(n^2 * k)O(k)只用来讲思路或极小数据测试枚举起点向右扩展固定 i找第一个合法 jO(n^2 * k)O(k)小规模数据逻辑直观标准滑动窗口双指针 missing/formedO(n k)O(k)固定字符集可视为 O(1)面试正解线上大数据候选位置优化滑动窗口只滑动 s 中属于 t 的字符位置O(n k)O(k)s 极长、t 字符种类少时更优这里n是s的长度k是t的字符种类数。标准滑动窗口里right和left各自最多移动 n 次每次更新都是常数级操作所以是 O(n k)。如果你把计数器固定成 128 长度的数组空间复杂度其实就是 O(1)。5.2 刁钻用例自我验证清单我平时写完滑动窗口习惯用下面这批用例做回归测试输入 s输入 t期望输出说明a空串边界a空串边界aaa单字符命中aaa数量不够aaaaaa单个窗口正好命中ADOBECODEBANCABCBANC典型用例ab字符缺失aaaaaaaaaaaaaaaa最左边连续三个 a 即合法aAbBcCabcaAbBc大小写敏感需要小写 a、b、c最后一个用例值得多说一句s aAbBcCt abc。注意s里有大写A也有小写a但我们需要的是小写a、小写b、小写c。从下标 0 的a开始窗口往下扩到下标 4 的c也就是aAbBc才同时包含小写a、b、c。中间没有任何一个更短的窗口能同时包含这三个小写字符所以答案是aAbBc。跑这些用例时我通常会再放一份枚举法代码做对拍。随机生成长度不等的字符串滑动窗口和枚举法输出应该完全一致。只要有任何一个用例不一致基本都是formed增减条件或者收缩顺序写错了。5.3 一种可选的进阶优化只滑动有效位置标准滑窗已经能过 LeetCode 原题但面试官可能会追问一句能不能再优化有一个思路是——只保留s中属于t的字符位置在这个稀疏序列上滑动窗口。道理很简单窗口两端只有落在t里的字符上长度才有机会缩短。中间那些不在t里的字符只是在计数时被动经过最后取s的下标算长度而已。from collections import Counter def min_window_filtered(s: str, t: str) - str: if not s or not t or len(s) len(t): return need Counter(t) positions [i for i, ch in enumerate(s) if ch in need] if len(positions) len(t): return window Counter() formed 0 need_size len(need) left_idx 0 ans for right_idx, pos in enumerate(positions): ch s[pos] window[ch] 1 if window[ch] need[ch]: formed 1 while left_idx right_idx and formed need_size: left_pos positions[left_idx] cur_len pos - left_pos 1 if ans or cur_len len(ans): ans s[left_pos:pos 1] left_ch s[left_pos] window[left_ch] - 1 if window[left_ch] need[left_ch]: formed - 1 left_idx 1 return ans这个版本的循环次数从n降到了“s中属于t的字符个数”。最坏情况下s全是t里的字符复杂度不变但实际场景里如果s很长、目标字符很稀疏收益非常明显。代价是代码多了一层positions可读性稍微下降。面试讲这一版能加分但不要为了炫技影响主版本正确性。5.4 实测表现大数据下的直观感受我在本地用长度 10^5 的随机字符串、长度 1000 的随机目标串做过对比。枚举版本几分钟都跑不完标准滑窗是毫秒级候选位置过滤版在目标字符稀疏时还能再快一倍左右。如果你手边没有测试环境也可以从复杂度上感受差距枚举是 O(n^2)滑窗是 O(n)差了三个数量级数据量一大就是天壤之别。实际写线上服务时如果不是特定场景标准滑窗已经足够。候选位置过滤更适合“海量文本里反复匹配同一批短关键词”这种前期预处理可以复用的场景。6. 面试怎么讲、变体怎么答6.1 面试现场的一种推荐表达顺序如果面试官让你现场做这道题不建议上来就闷头写滑动窗口。更好的节奏是第一步先确认题意。说清楚“覆盖”是指每个字符数量都不小于t中的数量t可能有重复字符大小写敏感。第二步抛最简单的思路。枚举起点向右扩展到第一个覆盖点复杂度 O(n^2 * k)数据量大时不行。第三步指出问题。每次枚举起点都重新计数大量窗口内容重叠被重复统计。第四步引出优化。左右指针都单调右移窗口计数可以复用复杂度降到 O(n)。这里可以提一句单调性随着 left 右移需要的 right 不会左移。第五步边写边讲。写need、window、formed的时候说明每个变量的含义重点解释为什么用判断达标。第六步自己跑例子。拿ADOBECODEBANC和ABC验证一下顺手补几个边界用例。这样一套下来比直接甩出完整代码更有说服力。6.2 高频相似题与套路迁移最小覆盖子串属于“滑动窗口定式”里的经典一题它的模板稍加改动就能迁移到很多题目无重复字符的最长子串第 3 题窗口内出现重复字符时收缩 left更新的是“最长”答案。字符串的排列第 567 题固定窗口长度等于len(t)检查窗口是否是t的排列。找到字符串中所有字母异位词第 438 题类似 567但把所有满足条件的起点都收集起来。替换后的最长重复字符第 424 题窗口内除了最多字符外的其他字符数不超过 k否则收缩。它们的统一骨架可以概括成left 0 for right in range(len(s)): 更新窗口状态 while 窗口不满足条件: 更新答案如果是找最短 收缩 left 更新窗口状态 更新答案如果是找最长第 76 题就是典型的“收缩前更新最短答案”。理解了这个模子面试遇到同族题目会轻松不少。6.3 我实际刷下来的一点心得这道题我自己刷了三遍才真正记住不是因为代码难而是因为某几个细节特别容易凭“感觉”写错。一个是formed必须用触发另一个是收缩循环里要先减计数再判断是否不达标还有一个是边界条件的兜底。每一条是独立的小坑单独看都简单串在一起就很容易翻车。我的建议是不要只背标准答案。先把枚举法写出来再用对拍的方式把它改成滑窗你才能真正理解“为什么双指针能省掉这么多计算”。这道题的价值不在代码本身而在你推导优化的过程。如果你准备面试还可以把这道题和 3、438、567 放在同一天刷彼此对照。你会发现它们其实是同一把尺子在量不同的物理量——有时候量最小长度有时候量最大长度有时候量固定长度。在第 76 题上花的时间会在这些相似题上连本带利赚回来。
