LeetCode 76 这道题我做过的次数大概比刷题列表里其他“困难”标签加起来还多。不是说它有多难而是它太适合拿来考察“滑动窗口”这个基本功了。面试里问“最小覆盖子串”本质上就是想看你能不能把双指针和窗口状态维护讲清楚。这题是有 O(n) 解法的而且这个 O(n) 不是玄学是严格可推导的。我第一次遇到这题的时候第一反应是暴力枚举所有子串然后逐个判断是否包含 t。这个思路没错但复杂度直接爆炸。后来老老实实把滑动窗口的进出逻辑理清楚才发现所谓的“困难”卡住的不是窗口本身而是怎么高效地判断“当前窗口是否已经覆盖了 t”。这篇就来完整拆一下 LeetCode 76从题目本身开始把滑动窗口的推导、代码实现、复杂度分析、以及我实际踩过的坑全部过一遍最后再聊几个面试官常见的延展问法。1. 题目还原与核心思路这个“困难”到底难在哪1.1 原题描述与最容易忽略的条件先看题面。给定字符串s和t要求在s中找到最短的一个连续子串使得这个子串包含t中的所有字符。注意“包含”不是简单的出现过而是t中每个字符出现的次数在窗口里都要满足。这个细节第一次刷题的人特别容易忽略。t AABC时窗口里必须至少有两个A、一个B、一个C少了任何一个都算没覆盖。题目还有一个隐藏条件如果s中根本不存在这样的子串就返回空字符串。这个边界情况看着简单但很多人写完代码后在窗口左边界移动时把答案覆盖成了空串最后返回了错误结果。后面会细说。1.2 暴力的复杂度瓶颈在哪暴力做法是枚举s的所有子串复杂度 O(n²)。每个子串再拿哈希表统计字符次数和t的统计结果比较又是 O(|s|) 级别的操作。整体一下就是 O(n³) 级别肯定过不了题目的长度限制。更关键的不是指数爆炸而是很多子串的统计其实在被反复计算。比如你计算了s[0..100]的字符统计马上又要计算s[0..101]只多了一个字符却把整个区间重新算了一遍。这种浪费在滑动窗口解法里会被彻底消除每次移动右指针时窗口只新增一个字符移动左指针时窗口只减少一个字符。2. 滑动窗口 O(n) 解法推导从直觉到不变量2.1 窗口的“进”与“出”维护一个动态区间滑动窗口的模型很简单两个指针left和right一开始都指向s[0]。right不断向右移动把新字符纳入窗口相当于“进”当窗口已经覆盖了t时尝试移动left缩小窗口相当于“出”。这个模型的关键在于窗口始终是一个连续区间你永远只改变两个端点不需要重新统计整个区间。用生活化的比喻你有一把尺子先在s上从左往右滑右侧不断扩展直到尺子里的字符种类和数量都满足了t的要求然后你开始从左边收缩尺子看还能不能保持满足。一旦收缩到不满足就又继续扩展右端。整个过程里每个字符最多被右指针扫描一次也被左指针扫描一次。2.2 用什么判断窗口已经覆盖了 t判断是这道题的解体关键。最直接的笨办法是每次窗口变化后把窗口的字符统计哈希表拿出来和t的统计哈希表逐项比对。这个操作是 O(字符集大小) 的。字符集如果固定为 128 个 ASCII 字符那还好但每次窗口移动都做一次 O(128) 的比较整个算法复杂度就从 O(n) 变成了 O(128n)虽然常数很小但写出来的逻辑不够优雅。更好的方案是维护一个valid计数表示当前窗口里有多少种字符已经达到了t的需求数量。具体来说先统计t中每个字符的需求量存入need。窗口扩展时如果新字符c在need中就把窗口计数window[c]加一并且当window[c] need[c]时说明c这个字符的覆盖要求已经达标valid加一。当valid need.size()时说明所有字符都达标了窗口有效。这个valid的思路本质上是从“比较两个哈希表”变成了“只维护一个整数”把判断成本从 O(字符集) 降到了 O(1)。2.3 为什么均摊下来是严格的 O(n)要证明是 O(n)核心是观察每个指针的移动次数。右指针right从头走到尾最多移动n次。左指针left虽然会在窗口收缩时频繁右移但它也是从0开始一路只能往右走不可能回退所以整个算法过程里left最多也移动n次。每次移动右指针做的事情是更新一个哈希表计数、可能更新一下valid都是 O(1)。每次移动左指针做的事情同理也是 O(1)。所以总操作次数是 2n 级别的常数倍再加上预处理t的 O(|t|)整体复杂度是 O(∣s∣ ∣t∣)。这里的 O(n) 不是平均意义下的概率结论而是严格均摊复杂度和快速排序那种“期望 O(n log n)”完全不同。这也是为什么这题能被当作“手写 O(n) 算法”的经典考题。3. 可直接复制的实现代码与关键行解读3.1 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 valid 0; // 有多少种字符已经达到覆盖要求 int left 0, right 0; int start 0, minLen INT_MAX; while (right s.size()) { char c s[right]; right; if (need[c] 0) { 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[d] 0) { if (window[d] need[d]) { valid--; } window[d]--; } } } return minLen INT_MAX ? : s.substr(start, minLen); } };3.2 Python 实现利用 Counter 和 defaultdictclass Solution: def minWindow(self, s: str, t: str) - str: from collections import Counter, defaultdict if not s or not t or len(s) len(t): return need Counter(t) window defaultdict(int) valid 0 left 0 start 0 min_len float(inf) for right in range(len(s)): c s[right] if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): if right - left 1 min_len: min_len right - left 1 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]3.3 代码里最容易写错的三个地方第一个是need和window的数组长度。题目虽然默认是大写小写英文字母但直接用vectorint(128, 0)是最保险的因为所有 ASCII 字符都覆盖了。如果只开26遇到大小写混合直接越界。第二个是左边界收缩时的valid更新顺序。必须先判断window[d] need[d]再执行window[d]--。反过来就错了因为window[d]--之后window[d]已经不满足need[d]了但此时valid还没有减少状态就出现短暂的不一致。第三个是收缩循环while (valid need.size())里是否每次都更新答案。我见过一种写法是把答案记录放在while外面只记录第一次进入循环时的状态。这样当窗口收缩后仍然覆盖t时就漏掉了更短的答案。正确做法是在每次收缩前都检查并更新答案。4. 实操踩坑记录与排查思路4.1 坑一重复字符导致“窗口长度等于 t 长度但没覆盖”调试s ADOBECODEBANC, t AABC时特别容易出这个现象。窗口长度可能已经大于等于t的长度了但t里的A出现两次窗口里如果只有一个A那就永远不算覆盖。这个坑的根源在于习惯性用“窗口长度是否大于等于 t 长度”来提前判断覆盖省去valid的比较。这种做法在某些简化版的滑动窗口题里确实成立但用在“最小覆盖子串”这里会直接错。排查方法也很简单在窗口收缩后打印window和valid肉眼检查每个字符的计数。真正验证通过的标准只有一个所有t中出现的字符window[c] need[c]全部成立。用valid need.size()去判断就是把这个条件压缩成了 O(1) 的比较。4.2 坑二左边界收缩时 valid 减错位置这是我最开始写的版本里反复出的问题。错误写法是这样的if (need[d] 0) { window[d]--; if (window[d] need[d]) { valid--; } }看起来逻辑没什么毛病先减少计数如果不够了就减少valid。但问题在于如果window[d]原来远远大于need[d]比如你需要 2 个A窗口里有 5 个A收缩掉一个A后window[d]变成 4仍然大于等于 2这时valid不应该变。上面的写法虽然结果上也不会让valid减少但有一种情况会出错当window[d] need[d]时先执行window[d]--此时window[d]变成need[d] - 1然后再判断window[d] need[d]会发现小于于是valid减一。这个结果是对的但逻辑顺序上容易让人忽略一个场景window[d] need[d]时收缩后依然window[d] need[d]这时不能减valid。按上面的写法判断条件window[d] need[d]为 false所以valid不变也没错。那为什么推荐“先判断后减少”呢因为这样写的语义更清晰先判断当前字符是否处于“刚好达标”状态如果刚好达标说明这个字符是整个窗口覆盖的必要条件移出它会导致覆盖状态被破坏因此valid减一然后才真正把它移除。否则用“减少后再判断”的写法会多一层条件容易写反。4.3 坑三字符集假设不同导致越界LeetCode 官方题目给的是英文字母但很多变体题会让你处理数字、空格、甚至 Unicode。如果直接用vectorint window(26)然后window[s[i] - a]遇到大写字符就直接变成负数下标了。我建议统一用128数组vectorint need(128, 0), window(128, 0);这样无论是字母、数字还是常见的英文标点都能覆盖。对于 ASCII 里的非英文字母虽然不常见但也不会越界崩溃。如果你遇到一个变体题明确说字符范围是a到z那可以用26数组省一点空间并配合- a操作。但面试时我不建议为了这点空间去增加出错概率直接128起步。4.4 坑四s 比 t 短时直接返回空串这个边界情况虽然简单但也容易写漏。如果s.size() t.size()那就算s里所有字符都用于覆盖数目上也不够直接枚举滑动窗口也没有意义。我一般会把这个判断放在函数开头提前返回空串省掉后续所有无谓操作。还有一种隐藏的边界情况是t为空字符串。题目一般会限制非空但为了稳妥加上判断也无妨。5. 面试现场和刷题计划里的延展问题5.1 变体一如果 t 中允许重复字符“最小覆盖子串”原题本身就允许t有重复字符所以这不是变体而是原题要求。但很多人会把这道题和“找到包含 t 所有字符的最短子序列”混淆后者不考虑重复次数。如果面试官上来先说字符不能重复那是降级版本反而好写。对于含重复字符的版本唯一需要强调的就是need.size()表示的是“不同字符的数量”而不是t的长度。比如t AABCneed.size()是 3不是 4。valid 3才代表三种字符都达标了。5.2 变体二如果要求返回覆盖次数而不是最短子串有些面试官会问直接统计有多少个子串满足条件或者统计有多少个最短覆盖子串的位置。这种情况我见过两种考法。第一种是求“覆盖次数”也就是s中有多少个不同的连续子串满足覆盖条件。这个问题直接用滑动窗口配合每个窗口内左指针的可移动范围来计数。难点在于左指针移动时窗口的覆盖状态变化是单调的所以可以维护一个有效区间的长度来累加。第二种是求“所有最短覆盖子串的起始位置”比如有可能存在多个长度相同的最短覆盖子串。处理方式是滑动窗口过程中当valid need.size()时把所有可能的左边界都尝试收缩并记录长度最小时的所有起始位置。注意去重因为同一个起点可能会因为收缩方式不同被记录多次。5.3 变体三如果 s 很长、t 很少如何进一步优化原题的 O(n) 已经是最优的大 O 复杂度了因为每个字符至少要被扫描一次才能判断覆盖状态。但在工程场景下如果s是一个上百 MB 的字符串t只有几个字符可以考虑先过滤掉s中不在t里的字符把原始的s压缩成一个“有效字符位置数组”然后只在这些位置上跑滑动窗口。这样可以把窗口的判断次数从n降低到s中的有效字符数量。这个优化在 LeetCode 上通常不需要但在实际日志分析或 DNA 序列处理场景里能省下不少时间。原理也很简单窗口里出现无关字符时它不会影响valid的变化白白增加一次字符串访问和哈希查找。我个人的习惯是刷题阶段先用标准的valid计数版本把思路跑通再单独用“压缩有效位置”的版本练习一下这样面到变体题时不会慌。这个优化思路在 “LeetCode 热门 100 题” 的滑动窗口分类里也可以横向迁移到其他类似题上比如 “找到字符串中所有字母异位词”它们的核心都是同一套双指针计数模型。最后再分享一个小技巧如果你在面试或者周赛中拿到这题写完代码后先自己在脑子里跑一个例子s AAAB, t AB就够用了。这个例子能同时验证重复字符、覆盖状态、收缩后依然覆盖这三个最容易出问题的点。跑通了再提交基本一遍过。