LeetCode 76困难滑动窗口 · 变长
最小覆盖子串 图解题解
在 s 里找包含 t 所有字母的最短子串，听起来难，其实一根伸缩橡皮筋就够了。
像用一根橡皮筋圈住货架找齐购物清单：右端不停往右扩，直到清单上所有商品都圈进来；然后左端往右收，把多余的边角料挤掉，圈到最小合法状态。再记下这段最短位置，右端继续前进——橡皮筋两端都只往右走，扫一遍找出最短覆盖段。
这道题到底在问什么
给字符串 s 和 t，在 s 里找出最短的子串，使它包含 t 的所有字母（含重复次数）。找不到返回空串。
- s
- "ADBC"
- t
- "BC"
- 输出
- "BC"
最优解：一步一步想明白
- 3把每个起点、每个终点都试一遍当然能做，但 n² 个子串里绝大多数明显不够格，白白检查，太慢。
- 4用 need 记下 t 里每个字母还差几个。右指针 r 不停吃字符，直到窗口把 t 全包住；这时再移左指针 l 把多余的左边挤掉，窗口能缩就缩、缩到不能再缩，就拿到一个最短候选。右扩只会让窗口更可能覆盖，左缩只在已覆盖时做——所以两根指针都不回头。
- 5need={B:1, C:1}, 还差 2 种先数 t="BC"：need = {B:1, C:1}，一共要凑齐 2 种字母才算覆盖。窗口从空开始。
- 6窗口 "A", 凑齐 0/2A 不是 t 需要的字母，吃进窗口但 need 不变，仍差 B、C 两种。
- 7窗口 "AD", 凑齐 0/2D 同样不需要。窗口 "AD" 还是没覆盖 t——这就是为什么不能急着检查、要让 r 继续扩。
- 8窗口 "ADB", 凑齐 1/2B 正是要的！need[B] 从 1 减到 0，凑齐种类数 +1。现在差 C 一种。
- 9窗口 "ADBC", 凑齐 2/2 覆盖！C 也吃进来，need 全部归零，凑齐数 = required = 2，第一次覆盖 t！记下候选 "ADBC"（长 4）。覆盖之后，轮到左指针登场——开始收缩。
- 10移除左端 A, l→1最左是 A，不是 t 要的，丢掉它窗口照样覆盖。l 前进到 1，窗口缩成 "DBC"（长 3），刷新最短。
- 11移除 D, l→2D 同样多余，丢掉，l 到 2。窗口缩成 "BC"（长 2）——更短了！继续试着缩。
- 12B 是必需的！缩了就破再想丢最左的 B——但 B 是 t 必需的！一旦丢掉，need[B] 弹回 1，覆盖被打破。这就是收缩的边界：缩到「再缩一步就不覆盖」就得停。所以 "BC" 是这一轮的最短。
- 13最短覆盖 = "BC"r 已到末尾、左边也缩到极限。整个过程里最短的覆盖子串是 "BC"，就是答案。
- 16「找最短的合法窗口」都是这个手感：r 扩到刚好合法，l 缩到再缩就不合法。判覆盖靠 formed == required，别去重排或重数整个窗口。
- 21把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：凭「窗口够长」就记答案，或随手重数整个窗口判覆盖
✓ 对：用 formed == required 判覆盖，恰好凑齐时才进 while 左缩并记最短
覆盖看的是「每种必需字母数量都够」，不是长度；formed 计数能 O(1) 判断，重数窗口会退化成 O(n·字符集)
✗ 错：收缩时只挪 l，不把 s[l] 加回 need / 不更新 formed
✓ 对：l 右移的同时 need[s[l]] += 1，若变正就 formed -= 1
丢掉的若是必需字符，覆盖已被打破，不回滚 formed 会继续错缩、答案偏短
完整代码（Python / C++ / Java）
Python
from collections import Counter
class Solution:
def minWindow(self, s, t):
if not s or not t:
return ""
need = Counter(t) # 每种字符还需要几个
required = len(need) # 要凑齐的「字符种类数」
formed = 0 # 窗口里已凑齐的种类数
window = {}
l = 0
best_len, best_l = len(s) + 1, 0
for r, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1 # 这一类刚好凑齐
while formed == required: # 已覆盖 → 试着左缩
if r - l + 1 < best_len:
best_len, best_l = r - l + 1, l
left = s[l]
window[left] -= 1
if left in need and window[left] < need[left]:
formed -= 1 # 缩掉后这一类不够了
l += 1
return "" if best_len == len(s) + 1 else s[best_l:best_l + best_len]C++
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty()) return "";
unordered_map<char,int> need, window;
for (char c : t) need[c]++;
int required = need.size(), formed = 0;
int l = 0, bestLen = s.size() + 1, bestL = 0;
for (int r = 0; r < (int)s.size(); r++) {
char ch = s[r];
window[ch]++;
if (need.count(ch) && window[ch] == need[ch]) formed++;
while (formed == required) {
if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
char left = s[l];
window[left]--;
if (need.count(left) && window[left] < need[left]) formed--;
l++;
}
}
return bestLen > (int)s.size() ? "" : s.substr(bestL, bestLen);
}
};Java
class Solution {
public String minWindow(String s, String t) {
if (s.isEmpty() || t.isEmpty()) return "";
Map<Character,Integer> need = new HashMap<>(), window = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int required = need.size(), formed = 0;
int l = 0, bestLen = s.length() + 1, bestL = 0;
for (int r = 0; r < s.length(); r++) {
char ch = s.charAt(r);
window.merge(ch, 1, Integer::sum);
if (need.containsKey(ch) && window.get(ch).intValue() == need.get(ch).intValue()) formed++;
while (formed == required) {
if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
char left = s.charAt(l);
window.merge(left, -1, Integer::sum);
if (need.containsKey(left) && window.get(left) < need.get(left)) formed--;
l++;
}
}
return bestLen > s.length() ? "" : s.substring(bestL, bestL + bestLen);
}
}套路模板 · 变长滑动窗口（背下来）
# 变长滑窗求「最短合法窗口」通用骨架
l = 0
for r in range(len(s)):
把 s[r] 加入窗口（更新计数 / formed）
while 窗口已合法（formed == required）: # 是 while 不是 if
更新最短答案 (r - l + 1)
把 s[l] 移出窗口；若某类不再够则 formed -= 1
l += 1
# 求「最长」则把记答案挪到 while 外复杂度
时间复杂度
O(n)
l 和 r 各自只向右走一遍，每个字符进窗口、出窗口各一次
空间复杂度
O(字符集)
need 最多存下 t 里的不同字母
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最小覆盖子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么 O(n) 判断覆盖？+
维护 need(每个字符还差几个)和 formed(已凑齐的种类数)；右扩时某类凑齐 formed+1、左缩时某类不够 formed−1，formed 达到 required 即覆盖。
为什么左右指针都只前进、就是 O(n)？+
每个字符最多被右指针加入一次、被左指针移出一次，总共 O(n)。
t 有重复字符怎么算？+
need 记的是数量，窗口里该字符够数才算这一种满足。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。