76. 最小覆盖子串

题目描述

给字符串 s 和 t，在 s 里找出最短的子串，使它包含 t 的所有字母（含重复次数）。找不到返回空串。

思路解析

所有起点终点都试一遍当然行，可大量子串明显不够格，白检查，太慢。

右指针往右拉，直到窗口第一次把 t 全包住；然后左指针往右挤，扔掉多余的字符，逼出最短。

记下 t 里每个字母还差几个（need）。窗口里凑齐一个就减一个，need 全部归零，就说明这一段已经把 t 包住了。

right 扩张中：从最左起步，窗口里只有 A，离「集齐 ABC」还差得远，右指针继续扩。

right 扩张中：右指针拉到下标 5，窗口 ADOBEC 第一次把 ABC 全包住。先把它记成候选（长 6），接着试着左缩。

left 收缩：左指针想往右挤，可左端的 A 是 t 需要的，丢了就缺 A，缩不动。记下 ADOBEC，右指针接着往后找下一个可行窗口。

就这样右扩、左缩交替推进，窗口像虫子一样往右爬，每凑齐一次就比一比谁更短。

继续滑动后：一路爬到右段，窗口落在 BANC，同样包住 ABC，但长度只有 4，比之前的 6 短，更新答案。

left 收缩：BANC 左端的 B 也丢不得，缩到头了。右指针也到尽头，最短覆盖子串就是 BANC。

变长滑窗的通用套路：右指针负责「够不够」，左指针负责「短不短」，用一个计数器判断窗口达没达标。

参考代码（Python）

1from collections import Counter
2def minWindow(s, t):
3    need = Counter(t); miss = len(t)        # 还差 miss 个字母
4    l = 0; best = (float(class="cl-str">"inf"), 0, 0)
5    for r, ch in enumerate(s):              # 右指针扩张
6        if need[ch] > 0: miss -= 1
7        need[ch] -= 1
8        while miss == 0:                    # 窗口已覆盖，左缩
9            if r - l + 1 < best[0]: best = (r-l+1, l, r)
10            need[s[l]] += 1
11            if need[s[l]] > 0: miss += 1
12            l += 1
13    return class="cl-str">"" if best[0] == float(class="cl-str">"inf") else s[best[1]:best[2]+1]

复杂度分析

• 时间复杂度：O(n + m) —— 左右指针各走一遍
• 空间复杂度：O(m) —— need 计数表

套路模板

所有变长滑窗都是这个骨架：右进、达标后左缩。求最短在 while 里更新答案，求最长则在 while 外更新——记住这点差别。

1l = 0
2for r in range(n):
3    加入 nums[r] 更新窗口状态
4    while 窗口已满足条件:
5        更新答案（这里求最短）
6        移出 nums[l]，l += 1

易错点

• ❌ 右指针一动就更新答案 → ✅ 窗口「满足条件」时才更新（求最短在 while 内）（没覆盖 t 的窗口不是候选，记了就错）
• ❌ 左缩时忘了把字母「还回」need → ✅ l 右移前 need[s[l]] += 1，缺了就 miss += 1（窗口缩小要同步恢复计数，否则后面判断全乱）
• ❌ 用 set 判断覆盖 → ✅ 用计数（Counter）（t 里字母可能重复，只看「有没有」会漏掉次数要求）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。