LeetCode 76最小覆盖子串几乎每个刷题的人都会在某个阶段正面撞上它。这道题在LeetCode热门100题里占着一个位置标着Hard难度但核心解法看起来又短得离谱——一个双指针循环两个计数数组十几行代码搞定。也正因如此网上关于它“到底是不是真O(n)”的争论从来没停过。今天不搬运题解我把这道题从题意到证明、从代码到调试完整拆一遍重点回答标题里那个问题O(n)解法存在吗如果存在它凭什么能做到O(n)1. 先读懂题意最小覆盖子串到底在问什么1.1 题面还原与三个容易忽略的细节题目原文很简单给你一个字符串s、一个字符串t请在s中找出包含t全部字母的最小子串。简单说就是从s里截一段连续字符这段字符必须把t里的每个字符都“覆盖”到而且长度要最短。但这里容易忽略三个细节。第一个t里的重复字符也要覆盖。比如t aa那子串里至少要有两个a只有一个a就不算覆盖。第二个要求的是子串不是子序列所以必须是连续的一段。第三个如果s里根本不存在这样的子串返回空串如果存在多个最短的返回任意一个即可。官方原题里说的是“保证答案唯一”但实际刷题时很多人第一时间拿不到样例就是因为没把这三个点刻在脑子里。举个题目自带的例子s ADOBECODEBANCt ABC。肉眼扫一遍最短覆盖子串是BANC。注意ABANC也覆盖了 ABC长度是 5但BANC是 4所以它才是答案。1.2 暴力解为什么不行从O(n³)到O(n²)的真实成本很多人刚看到这道题第一反应是暴力枚举。枚举s的所有起点i和终点j得到 O(n²) 个子串再逐个判断每个子串是否覆盖t。判断过程如果重新统计子串字符并和t的需求做比较单个判断又是 O(len(s))所以总复杂度是 O(n³)。哪怕用前缀和数组优化把单次判断降到 O(字符集大小)整体也还是 O(n²) 级别在s长度到十万、百万这个量级时基本没法用。暴力慢的本质在于大量信息被重复计算。相邻两个子串之间只差一个字符但暴力解法会把它们各自的字符统计完全重算一遍。这就像你要统计一栋楼每层有多少人但每次统计都把整栋楼重新跑一遍显然不合理。滑动窗口做的事情恰恰是把这种“基于上一个结果增量更新”的复用做到极致。2. 滑动窗口的完整推导O(n)解法是怎么想出来的2.1 从“最短”二字出发窗口扩展与收缩的直觉“最短子串”这四个字天然指向滑动窗口。我们先定义一个窗口区间[left, right]表示当前正在考察的s的子串。想象你拿着一把可以拉长缩短的尺子在字符串上移动。第一步右指针right不断向右扩展窗口每纳入一个新字符就把它记到一个计数器里。第二步一旦发现当前窗口已经覆盖了t的所有字符就尝试把左指针left向右收缩也就是把窗口左侧的字符一个一个丢出去。为什么敢丢因为当前窗口已经满足覆盖条件丢掉左边多余的字符有可能让窗口变得更短而如果丢掉之后仍然满足覆盖条件那我们就得到了一个更短的候选答案如果丢掉之后不满足了说明这个长度已经是“以当前 left 为起点”的极限那就停手继续向右扩展right寻找下一个可能的更短窗口。这里有一个非常重要的直觉窗口的扩展和收缩方向都是单向的。right只会向右走left也只会向右走两个指针都不会回退。这意味着整个算法最多把s从头到尾扫两遍——一遍是right扩展一遍是left收缩。这正是 O(n) 解法的根本来源。2.2 关键优化用formed/required做O(1)覆盖判断滑动窗口的框架并不难懂真正的核心难点在于怎么快速判断当前窗口是否覆盖了t最朴素的做法是每次窗口变化后把t的需求哈希表和当前窗口的计数哈希表整体比较一遍。但这样一次比较就是 O(字符集大小)窗口总共变化 O(n) 次整体就退化成了 O(n·字符集)虽然字符集是常数但在字符范围大或数据量大的场景下就不是严格的 O(n)。更聪明的方式是引入两个概念required表示t中“不同字符的种类数”formed表示当前窗口中“已经满足需求数量”的字符种类数。当formed required时说明每种字符都已经达到或超过需求数窗口必然覆盖了t。每次右指针纳入字符c时只需要让窗口计数加一然后比较窗口里c的数量是否恰好等于t对c的需求数如果相等就formed。每次左指针丢出字符时做对称的反向操作。这样判断覆盖状态就从“全量比较”降到了单次 O(1) 的“计数比较”这也是整套算法能称为严格 O(n) 的关键一步。3. 可提交的C实现与逐行注释3.1 完整代码与运行效果先把可以直接提交的 C 代码放出来我加上了逐行注释class Solution { public: string minWindow(string s, string t) { // need记录t中每个字符的需求数量required记录t中有几种不同字符 vectorint need(128, 0); int required 0; for (char c : t) { if (need[c] 0) required; need[c]; } // window记录当前窗口中每个字符的出现次数 vectorint window(128, 0); int left 0, right 0; int n s.size(); int minLen n 1; // 最小长度初始化为比s长度还大方便判断是否找到 int start -1; // 最小覆盖子串的起始位置 int formed 0; // 当前窗口已经满足需求数的字符种类数 while (right n) { // 1. 右指针扩展窗口 char c s[right]; window[c]; if (window[c] need[c]) { formed; // 字符c的窗口计数恰好达到需求 } // 2. 窗口已经覆盖t的全部字符尝试收缩左指针 while (formed required) { int len right - left 1; if (len minLen) { minLen len; start left; } // 丢掉窗口最左侧的字符 char d s[left]; window[d]--; if (need[d] 0 window[d] need[d]) { formed--; // 字符d的需求被破坏覆盖状态失效 } left; } right; } return start -1 ? : s.substr(start, minLen); } };配合题目样例测试s ADOBECODEBANCt ABC运行结果BANC。再测几个边界s at a返回as at aa返回空串s abct abcd返回空串。结果都符合预期。3.2 三个最容易被判错的细节第一个细节formed的条件为什么是window[c] need[c]而不是因为会导致formed只增不减窗口后丢失字符时无法正确反映覆盖状态被破坏。用严格相等配合丢字符时对称判断window[d] need[d]才能做到状态精准切换。第二个细节记录答案的位置必须在left收缩之前。很多人习惯先收缩再记录这样当窗口被收缩到刚好不满足覆盖条件时真正的边界就被跳过了。比如s BANC、t ABC如果先丢B再记录那以B开头的BANC就永远记录不到。第三个细节minLen的初始值应该设为n 1而不是 0 或一个大整数。设成n 1的好处是可以直接用start -1判断无解语义很清晰。如果你非要用INT_MAX最后判断无解时也别看着minLen发呆记得先看start。4. 为什么是O(n)复杂度证明与直觉4.1 每个字符最多进出窗口各一次严谨地说这个算法的时间复杂度不是“差不多 O(n)”而是严格 O(n m)其中 m 是t的长度。原因很简单初始化need需要遍历一遍t这是 O(m)。主循环里right指针从 0 扫到 n-1每个字符只会因为right扩展而进入窗口一次left指针从 0 最多扫到 n-1每个字符也只会因为left收缩而离开窗口一次。有人可能会问内层while (formed required)不是可能在一个right步内循环很多次吗没错但它循环的次数总和是有限的。因为left每执行一次left就有一个字符永久离开窗口而left最大只能到 n所以内部循环整体执行次数不超过 n。两个指针各自的移动次数加起来是 2n再加上每次移动内部都是常数次数组操作所以总复杂度是 O(n)。这就是“滑动窗口”这道题最核心的复杂度论据。4.2 与“伪O(n)”写法的分水岭我在评论区见过不少题解也说自己是 O(n)但实现里每次窗口变化都调用一个函数去比较两个哈希表。这种写法的复杂度严格说应该是 O(n·K)K 是字符集大小。当字符集只有 26 个字母时K 是常数所以理论上还是 O(n)但如果字符集扩展到 Unicode或者面试官把数据规模调到一千万这种写法就会立刻露出疲态。真正的分水岭在于“覆盖状态”的维护方式。用formed和required做增量维护每次窗口变化只需要常数次操作这才是被大家公认的标准 O(n) 写法。所以“有没有O(n)解法”这个问题的答案是有而且必须基于状态计数而不是全量比较。5. 常见bug与调参实录5.1 formed更新条件的经典翻车现场我调试过很多次这个代码最常翻车的点集中在formed的更新上。有人会写成if (window[d] need[d]) { formed--; }这样少了need[d] 0的判断。当d不是t中的字符时need[d] 0而window[d]很可能比 0 大丢出去之后window[d]仍然 0此时如果贸然formed--就会把“覆盖状态”错误地破坏掉导致后续窗口明明已覆盖却无法进入记录循环。这个 bug 非常隐蔽因为只会在特定字符序列下触发我建议你在写的时候养成先判断need[d] 0再动formed的习惯。另一个翻车点是记录答案的位置。我还见过有人把len的更新写到内层while的末尾导致每个left收缩后的子串都被记录一遍虽然也能找到最短但逻辑不清晰而且容易记录到不满足覆盖条件的窗口。记住一个原则“先记录再收缩”。5.2 数组与unordered_map的选择标准题解里用vectorint(128)也就是 ASCII 字符集范围这个大小对题目足够了。有些初学者习惯用unordered_mapchar, int也没问题但要记得配合formed做增量判断不要每次全量遍历 map。两者的实际表现差异在数据量小时几乎看不出来但用数组有几个好处初始化零、下标访问快、不用处理find时end()的边界问题。缺点是你得明确字符集范围如果遇到扩展 ASCII 码到 255 的情况记得把数组开成 256。如果是面试场景我更推荐用数组实现写完代码后主动说一句“这里假设字符集为 ASCII所以用 128 长度的数组如果字符集更大我会换成哈希表并保持同样的增量计数思路”这句话会让面试官觉得你对空间复杂度有意识。5.3 从测试用例到边界处理的套路刷这道题时我沉淀了一套自测用例模板。除了题目自带的样例你至少该测这几组第一组s为空串或t为空串注意t为空属于极端的边界题目一般没说不允许但你的代码得能处理“required 为 0”的情况标准解法里required0时formedrequired恒成立内层 while 会直接收缩到窗口为空最终返回空串这也是合理的解释第二组t的长度大于s这种无解场景要确保返回空串而不是越界第三组窗口恰好是s的一个前缀比如s AB、t A此时start指向 0移动逻辑要保证不会丢解。我用这几组用例把代码跑一遍基本能覆盖 90% 的隐藏雷区。剩下的坑多数是题目描述里没提但测试数据里埋着的字符类型问题这时就可以用int[128]的宽字符集方案一劳永逸。6. 以76题为轴心滑动窗口题串与变式扩展6.1 同框架题目对比表76 题所在的滑动窗口家族在 LeetCode 刷题列表里反复出现。它们的代码骨架几乎一样右指针扩展左指针收缩计数器维护状态。区别只在于收缩条件和返回目标。我把这个题串整理出来你可能刷完 76 之后会发现后面连续几道题都像老朋友题号题目窗口类型收缩条件返回目标76最小覆盖子串变长窗口formed required最短覆盖子串3无重复字符的最长子串变长窗口当前字符已在窗口内重复最长无重复子串567字符串的排列固定窗口窗口长度等于t长度是否存在包含排列的子串438找到字符串中所有字母异位词固定窗口窗口长度等于t长度所有匹配起点30串联所有单词的子串固定窗口窗口长度等于单词总长所有匹配起点我自己的刷法是先彻底搞懂 76 的增量计数再做 3 题时把“重复”的维护换成if (window[x] 1)的收缩条件做到 567 和 438 时把“变长窗口”改成“固定长度窗口”。这样从一道题能牵出一串题比暴力刷完 100 道题效率高得多。6.2 面试中的追问与扩展这道题在面试里被追问的频率也很高。常见追问包括如果t是一个单词列表s是正文要你找包含所有单词的最短子串这就变成 LeetCode 30本质上还是滑动窗口只是把字符计数换成了单词哈希如果要求返回所有最短子串而不是只返回一个那就需要记录多个起点并且最后汇总如果字符集可能超过 ASCII怎么调整空间复杂度我的回答思路是用动态哈希表代替固定数组但必须保留formed计数做增量维护否则复杂度会退化为 O(n·K)。还有一个很实际的问题面试官可能会问你“这题用 O(n) 解法的前提是什么”。我会回答前提是窗口的扩展和收缩都是单向的而且覆盖状态的判断能够做到 O(1)。如果题目改成“允许子串内的字符顺序任意但必须是最短超序列”那就是另一类问题了滑动窗口框架就需要改造。把这层想明白说明你不是背模板而是真的理解了双指针背后的单调性。我个人刷这道题最大的心得体会是LeetCode 76 真正的分水岭不在于“想到滑动窗口”而在于“怎么把覆盖判断从全量比较降到增量维护”。很多 Hard 题看起来抽象但拆解到最后就是一个“用额外状态换比较时间”的取舍。如果你也正在被这道题折磨不妨先别急着看题解亲手把暴力解写一遍再观察相邻子串之间差在哪里那个观察就是你通向 O(n) 的钥匙。