1. 先搞清楚最小覆盖子串到底在找什么聊一道很经典的字符串题最小覆盖子串。题目给两个字符串 s 和 t要求从 s 里找出一个最短的连续子串让它包含 t 中的全部字符而且每个字符的数量也要满足如果找不到就返回空串。刚接触这道题的时候大多数人不是看不懂题意而是卡在怎么高效判断窗口已经覆盖 t以及缩短窗口时计数器怎么维护这两个地方。这篇文章把这两个核心问题拆开讲透顺便把代码里那些容易写错的细节和效率优化一起列出来适合已经掌握基本双指针概念、想彻底搞定滑动窗口问题的读者。1.1 覆盖不是包含顺序也不重要先看一个最常见误解覆盖不等于出现过。如果 t AABC那么 s 里的窗口必须包含两个 A、一个 B、一个 C少一个都不行。比如窗口BACA里有 A 两个、B 一个、C 一个算覆盖窗口AC虽然也出现了 A 和 C但 B 没有而且 A 的数量不够就不能算。这里强调的是字符出现的次数不是字符种类是否齐全。还有一个容易混淆的点子串是连续的不能像子序列那样跳着取。题目要求的是 s 中一段连续区间。不过窗口内部字符的顺序完全无所谓t ABC窗口CBA也能覆盖。这个特性决定了我们只需要统计字符频率不需要关心相对顺序为后面用哈希表或数组计数扫清了障碍。1.2 暴力解法的问题最直观的做法是枚举所有子串也就是先固定左端点 i再让右端点 j 从 i 一直走到末尾对每个子串都检查一遍是否覆盖 t。检查覆盖需要统计窗口内每个字符的出现次数再逐个和 t 的需求比对。这样做的复杂度大概是 O(n^2 * m)n 是 s 的长度m 是 t 的长度。如果 s 是一万个字符这个算法基本就跑不动了如果 s 是十万、百万级别暴力枚举更是直接不可行。暴力解法虽然慢但它给了两个重要信息一是我们必须用字符频率来刻画覆盖关系二是窗口在向右扩展的过程中很多枚举区间是重复的。比如从 i0 开始已经找到覆盖区间 [0, 5]那么从 i1 开始就没必要重新从 j1 逐个向右扫完全可以在之前的状态基础上继续移动这就是滑动窗口的出发点。2. 为什么只有滑动窗口适合这题单调性是关键滑动窗口并不是万能的它成立的前提是窗口变化具有单调性。所谓单调性就是右指针不需要回头。这一点对于 76 题来说特别重要因为一旦不能单方向移动复杂度就会退化。2.1 窗口扩展-收缩的单调性直觉如果我们固定左端点 left为了达到覆盖条件需要不断把右端点 right 往右移动。第一次让窗口覆盖 t 的时候我们就得到了以 left 开头的最短覆盖子串。这时候如果 left 向右移动窗口会变小原本覆盖的状态可能就失效了要继续恢复覆盖只能继续向右移动 right让新的字符进入窗口。right 绝对不需要往左退因为 left 已经右移丢失的字符不可能在左边补回来。这个过程可以类比成一根橡皮筋右端不断向右拉伸直到窗口能包住目标集合然后左端向右收紧压缩橡皮筋长度一旦压缩过头右端再继续向右拉伸。两端都只往一个方向走整个遍历就是线性推进的。2.2 收缩时的关键决策窗口进入覆盖状态后我们要尝试右移 left 来缩短窗口。注意收缩过程不一定只移动一步就停如果窗口里有多余字符移走一个后窗口可能仍然覆盖 t那就可以继续收缩一直收缩到窗口不再覆盖才回到扩展阶段。这里的多余字符可以是 t 中不存在的字符也可以是 t 中某个字符超出需求数量的部分。需要特别提醒的是答案的记录时机通常放在收缩过程之中。因为每完成一次有效的 left 右移窗口仍然覆盖且长度更短这可能就是新的最小值。如果只在 while 循环外面记录一次很容易漏掉收缩到一半时出现的更短窗口。2.3 线性复杂度的保证为什么左右指针可以总共只移动 O(n) 次因为 left 最多从 0 移动到 n-1right 也最多从 0 移动到 n-1两个指针都不会回退。每次移动只需要 O(1) 的时间更新计数所以总复杂度是 O(n)。这是滑动窗口相比暴力枚举的核心优势但前提是判断窗口是否覆盖也要做到 O(1)。如果每次还要重新扫描窗口复杂度就又会涨回去这个点我在后面优化部分会专门展开。3. 窗口状态怎么记录need 数组和 valid 计数的完整语义现在来到了这题最核心的地方怎么用一份缺口单管理窗口状态并且用 O(1) 时间回答窗口是否覆盖 t。3.1 need 数组不是窗口里有什么而是窗口还缺什么常见实现里有一个数组 need但很多初学者误以为它记录的是窗口内字符的出现次数。其实它记录的是相对于 t 的需求窗口还缺多少个字符。初始化时遍历 t把每个字符的需求量写进 needneed[A] 2 表示还缺两个 A。当右指针扩展时新字符进入窗口它补上了一个缺口所以 need[ch] 减 1。当左指针收缩时字符离开窗口它重新变成缺口的一部分所以 need[ch] 加 1。need 的数值有三种含义大于 0 表示这个字符还缺多少个等于 0 表示这个字符不多不少刚好满足小于 0 表示窗口里这个字符已经超出需求多了多少个。比如 need[A] -1就说明窗口里的 A 比 t 要求的还多一个。3.2 valid 为什么按字符种类计不按字符数量计valid 是一个计数器记录的是已经满足需求的字符种类数。t 中可能存在重复字符比如 AABC它有三个不同字符 A、B、C所以最终需要让 valid 等于 3也就是三个字符种类都补齐了。valid 加一和减一的时机非常关键它不是在 need 变成负数或正数时变化的而是在从缺到不缺或从不缺到缺这个转换瞬间变化。右指针加入一个字符后如果 need[ch] 恰好从 1 变成了 0说明这个字符刚刚补齐valid 加一。左指针移除一个字符后如果 need[ch] 恰好从 0 变成了 1说明这个字符从刚好够变成了缺失valid 减一。至于 need 从 2 减到 1那只是缺口缩小并没有补齐need 从 -1 减到 -2也只是多出来更多valid 不该变化。反过来need 从 -1 加到 0说明多出来的一个被移走了但字符本身仍然刚好够也没有新的缺口产生valid 同样不该变化。理解这个转换点整段代码就不会写错。3.3 模拟一次完整的状态迁移用一个小例子把状态变化走一遍。设 s CAABACt ABC。初始时 need {A:1, B:1, C:1}valid 0目标 valid 数 3。操作窗口内容need 状态(A,B,C)valid是否覆盖右移加入 CC(1,1,0)1否右移加入 ACA(0,1,0)2否右移加入 ACAA(-1,1,0)2否右移加入 BCAAB(-1,0,0)3是记录长度 4左移移除 CAAB(0,0,1)2否停止收缩右移加入 AAABA(-1,0,1)2否右移加入 CAABAC(-1,0,0)3是长度 5左移移除 AABAC(0,0,0)3是长度 4左移移除 ABAC(1,0,0)2否停止收缩结果得到最短覆盖子串 BAC长度为 3。注意收缩过程中有时候移除的是多余字符比如从 AABAC 移除第一个 A 时need 从 -1 变回 0valid 不变再移除一个 A 时need 才从 0 变成 1valid 才减一。这个细节如果只靠背代码很容易理解偏差。4. 代码详解数组版和哈希表版先说一个我实际写代码时的习惯核心逻辑我通常用数组实现给读者讲原理时再用哈希表解释。因为数组版更贴近底层性能也更好哈希表版可读性更高但存在额外开销。两边都写出来遇到什么场景都能直接应对。4.1 数组版完整代码def minWindow(s: str, t: str) - str: if len(s) len(t): return # 1. 初始化需求数组ASCII 字符用 128 足够 need [0] * 128 for ch in t: need[ord(ch)] 1 # 2. 统计 t 中有多少种字符作为 valid 的目标值 need_cnt sum(1 for v in need if v 0) left 0 matched 0 start 0 min_len len(s) 1 for right, ch in enumerate(s): # 3. 右指针扩展进入窗口的字符补上一个缺口 idx ord(ch) need[idx] - 1 if need[idx] 0: matched 1 # 4. 窗口覆盖 t 后尝试收缩左边界 while matched need_cnt: cur_len right - left 1 if cur_len min_len: min_len cur_len start left left_ch s[left] left_idx ord(left_ch) need[left_idx] 1 if need[left_idx] 0: matched - 1 left 1 return if min_len len(s) 1 else s[start:start min_len]4.2 关键步骤逐行说明先看初始化部分。提前判断len(s) len(t)可以直接返回空串因为 s 长度都不够根本不可能覆盖 t。这里的 need 数组用了 128Python 的ord会把字符转成 ASCII 码大小写英文字母都在这个范围内。need_cnt是需要满足的字符种类总数比如 t AABCneed_cnt 3。再看不变量更新。右指针移动时无论进来的字符是不是 t 需要的都会执行need[idx] - 1。如果这个字符是 t 外的字符need 会变成负数但它永远不会触发need[idx] 0其实可能触发如果该字符初始 not in need那么初始是 0减去 1 变成 -1不触发。只有那些初始为正数的字符减到 0 时才会触发 matched 加一。也就是说matched 只统计真正从缺到不缺的种类。收缩判断条件need[left_idx] 0是这段代码最容易写错的地方。当左指针移出一个字符时need 加一。如果加一后大于 0说明这个字符从刚好满足变成了缺失matched 减一如果加一后仍然小于等于 0说明这个字符原本就是多余状态移走一个不足为奇覆盖状态没有破坏。4.3 哈希表版完整代码from collections import Counter def minWindow_map(s: str, t: str) - str: if len(s) len(t): return need Counter(t) need_cnt len(need) window Counter() matched 0 left 0 ans (float(inf), 0, 0) for right, ch in enumerate(s): window[ch] 1 if ch in need and window[ch] need[ch]: matched 1 while matched need_cnt: if right - left 1 ans[0]: ans (right - left 1, left, right) left_ch s[left] window[left_ch] - 1 if left_ch in need and window[left_ch] need[left_ch] - 1: matched - 1 left 1 return if ans[0] float(inf) else s[ans[1]: ans[2] 1]哈希表版的逻辑和数组版完全一致区别在于window记录窗口内真实频次need记录目标频次。判断覆盖时如果某个字符在窗口的出现次数恰好到达需求值matched 加一如果移出后低于需求值matched 减一。哈希表更直观但 Counter 是通用数据结构每次访问键值都有哈希开销。4.4 两个版本的取舍对比维度数组版哈希表版可读性中等理解 need 的负数语义需要时间较高window 和 need 语义接近直觉时间常数小索引访问 O(1)大哈希查表有额外开销字符集限制适合 ASCII若扩展 Unicode 需扩容无限制适合任意字符面试/笔试推荐输入为英文字母时推荐逻辑讲解时推荐如果题目明确只有大小写英文字母我会优先选择数组版。如果是通用场景或者字符集不确定哈希表版更保险。两个版本我都建议亲手写一遍尤其是数组版能加深对缺口单这个模型的理解。5. 效率优化从 O(N*M) 到 O(N) 的进化路线这一节集中说说性能问题。很多人能写出正确代码但常数很大或者判断覆盖时多扫了一层循环结果在大数据量下表现很差。5.1 最常见的低效写法是什么最容易出现的坏写法是扩展右指针后每次都调用一个check()函数重新统计窗口内所有字符频次再和 t 的需求比对。比如这样def is_valid(s, left, right, need): window Counter(s[left:right1]) for ch in need: if window[ch] need[ch]: return False return True这种写法每次判断都要新建一个 Counter复杂度至少是 O(窗口长度)。加上外层 for 循环整体会退化到 O(n^2) 甚至 O(n * |t|)。在大字符串上运行时间会急剧膨胀。问题不是出在统计频次本身而是每次移动指针都重新统计了全窗口丢弃了之前的状态信息。5.2 valid 变量究竟省在哪里滑动窗口的精髓是增量维护状态右指针加入一个字符只需要更新一个计数左指针移除一个字符也只更新一个计数。判断是否覆盖时不需要重新扫窗口只需要看 valid 是否等于 need_cnt。这个从每次扫描窗口到维护一个整数的变化正是 O(n * m) 变成 O(n) 的关键。如果觉得 valid 不好理解可以换一种说法valid 记录的是目前已经有多少种字符恰好满足需求。窗口覆盖 t等价于所有字符种类都满足了也就是 valid need_cnt。每次只在一个字符的计数从缺变为不缺或从不缺变为缺时valid 才变化一次。由于每个字符的计数变化方向只有一次到多、多到少的切换所以总变化次数也是 O(n) 量级。5.3 数组代替哈希表和提前终止代码层面的优化有三件小事值得做。第一用定长数组代替哈希表避免每次Counter的哈希计算和内存分配。第二初始化时顺便统计need_cnt不用每轮再遍历整个 need 数组检查是否都满足。第三可以加一个提前终止的判断如果当前剩余字符串长度已经不可能超过当前最短长度直接结束循环。一个可行的提前终止写法是在主循环内部根据当前 min_len 判断for right in range(len(s)): if len(s) - right min_len: break # ... 扩展逻辑这个判断放在扩展逻辑之前意思是从当前 right 到末尾的剩余总长度都不足 min_len 了那即使后面全都能覆盖也不可能产生更短的窗口直接退出。注意这个优化只在已经找到有效答案之后才有意义如果 min_len 还是初始的 len(s)1这个判断永远不会触发。5.4 只遍历候选字符位置长字符串加速技巧还有一个更激进的优化思路适合 s 很长、t 很短、t 的字符在 s 中出现稀疏的场景。既然 s 中大量字符和 t 无关那可以让双指针只跑在有可能影响状态的位置上。做法是先用一个列表记录 s 中所有属于 t 的字符的下标比如pos [i for i, ch in enumerate(s) if need[ord(ch)] 0]注意这个need要提前初始化好ord(ch)在 need 中对应值大于 0说明该字符在 t 里出现过。然后双指针 left_idx 和 right_idx 在这个 pos 列表上移动但计算窗口真实长度时要用pos[right_idx] - pos[left_idx] 1。这个优化把主循环从遍历整个 s变成只遍历 s 中相关字符的位置。如果 s 长 10 万但相关字符只有 100 个主循环直接从 10 万轮降到 100 轮。代价是代码更绕容易把位置数组的下标和真实字符串下标搞混。我的建议是笔试中先写基础的数组版保证正确如果性能确实成为瓶颈再引入这个技巧。6. 易错点与边界 Case 复盘写这题时容易踩的坑我基本都踩过一遍这里集中复盘几个最典型的。6.1 用 Set 判断覆盖字符种类骗局有的代码会用一个 set 记录 t 的字符然后判断窗口是否包含 set 中的所有元素。这个做法在 t 所有字符都不重复时才勉强成立。一旦 t 存在重复比如 t AAs BA窗口 BA 中确实出现了 Aset 会认为已经覆盖但实际还需要两个 A。这是最隐蔽的数量错误。覆盖判断必须落到每个字符的需求量上而不是字符种类上。6.2 收缩判断条件写成 0 的后果再看数组版收缩时那行代码如果写成if need[left_idx] 0而不是 0会发生什么考虑一个已经覆盖但有多余 A 的窗口移除一个多余的 A 时need 会从 -1 变回 0。字符明明没有从够变缺valid 不应该变化但如果条件写成了 0这个场景下 need 从 -1 变 0 后等于 0会误判为字符缺失导致 valid 错误减一。紧接着窗口明明仍覆盖 t却因为 valid 不满足要求错过了一个可能的更短窗口。判断条件只需要关心是否从 0 变成正数所以 0才是正确写法。6.3 答案更新位置和 min_len 初始值答案更新一定要放在 while 收缩循环内部而不是 while 循环结束之后。原因我在第 2.2 节提过一次收缩过程中可能连续移出多个多余字符中间窗口仍然覆盖且更短这些长度都必须参与比较。如果只在退出 while 后更新会漏掉中间状态。至于 min_len 初始值我习惯用len(s) 1既方便最终判断是否找到答案又避免用inf导致后续类型混乱。6.4 一组值得手推的边界用例st期望结果ADOBECODEBANCABCBANCaaaaaaabbbaBababdbcaabcbcaaaaaaa这些用例虽然短但每一个都覆盖一种边界情况空结果、单字符匹配、重复字符不足、大小写敏感、覆盖子串在中间。写完代码后我建议把这几个用例都跑一遍能跑通基本就稳了。7. 举一反三从 76 题到滑动窗口模板这道题绝不仅仅是背一个答案它背后的滑动窗口模板可以迁移到一整个题目家族。这里我把模板抽出来再说说怎么改造成其他题型。7.1 通用模板四步走滑动窗口几乎所有变体都可以归纳成四步一看需求容器二扩展右端三收缩左端四更新答案。需求容器可以是数组、哈希表也可以是一个计数器核心是能表达当前状态是否满足题目条件。扩展右端时更新状态当状态满足条件时进入收缩阶段收缩阶段每次移动左端同时更新答案。最后循环结束根据记录的结果返回。具体到 76 题条件就是窗口覆盖 t。对另一类题目条件可能是窗口内没有重复字符也可能是窗口长度恰好等于某个固定值。变化的是条件判断不变的是双指针的单向移动框架。7.2 相关变形题与调整点有一类题是判断一个字符串是否包含另一个字符串的排列。这类题可以直接套用本题模板但收缩条件要换成窗口长度等于 t 的长度而且一旦找到就立即返回。还有一类题是找出所有异位词的起始位置同样需要固定长度窗口并在移动过程中比较窗口频次和目标频次是否相等。另有一类题要求最长无重复子串这类题甚至更简单因为条件是窗口内无重复不满足时收缩左端直到重建合法状态即可。这些变形题核心都没变搞清楚什么条件进入收缩阶段答案在什么时候更新状态如何增量维护就能从一道 76 题打通一串题目。7.3 我建议的练习顺序和习惯我的个人做法是第一次接触时不要只背代码用一个短例子手动推一遍 need 和 valid 的状态变化尤其是负数区域的变化。推完再对照数组版代码写上几遍直到闭着眼睛也能把收缩条件写对。之后再做变形题时先把模板四个步骤写在草稿纸上再填这套题的条件和答案更新时机。最后分享一个小技巧每次写完 76 题我会强制自己把数组版和哈希表版各写一遍再故意改坏一个条件比如把 0改成 0观察结果会不会出错。这样既加深了对缺口单模型的理解也把最容易错的边界条件焊死在记忆里。能把这个过程走完滑动窗口这类题基本不会再翻车。