困难LeetCode 76可逐步演示引导学习
最小覆盖子串
可变窗口：先扩大，再收缩
用 need 记录 t 还欠每个字符多少个；右指针扩大窗口直到覆盖 t，再移动左指针尽量缩小窗口，过程中记录最短答案。
时间复杂度 O(n + m)空间复杂度 O(m)
题单：面试热题
题目描述
给定字符串 s 和 t，在 s 中找出最短的连续子串，使它包含 t 中所有字符（包括重复次数）。如果不存在，返回空字符串。
学习目标
说清右扩找可行解、左缩找最优解的流程，写出 O(n+m) 覆盖子串。
已完成 0 / 6 阶段
诊断
窗口何时可行
怎么判断窗口覆盖了 t？
建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。
解题思路
核心思想
用 need 记录 t 还欠每个字符多少个；右指针扩大窗口直到覆盖 t，再移动左指针尽量缩小窗口，过程中记录最短答案。
为什么需要它
枚举所有子串是 O(n²) 以上。窗口右扩只增加一个字符、左缩只减少一个字符，欠账表可以增量维护，所以判断当前窗口是否覆盖 t 是 O(1)。
第一反应：直觉方案
对每个起点向右扫描，直到覆盖 t，再记录长度；能工作，但起点每次重来，重复计算很多。
关键洞察
覆盖 t 后，窗口里可能包含大量多余字符；此时不断左移，直到再移就失去某个必需字符为止，这个位置就是当前右端下最短的窗口。
时间复杂度 O(n + m)空间复杂度 O(m)
易错点
- need 记录还欠多少，数量为 0 后仍保留 key。
- 丢失必需字符时 missing 要重新增加。
- t 为空、无解时返回空字符串。
逐步演示
参考代码
1function minWindow(s, t) {
2 if (t.length === 0 || s.length < t.length) return '';
3
4 const need = new Map();
5 for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
6
7 let missing = t.length;
8 let left = 0;
9 let start = 0;
10 let minLen = Infinity;
11
12 for (let right = 0; right < s.length; right++) {
13 const ch = s[right];
14 if (need.has(ch)) {
15 if (need.get(ch) > 0) missing--;
16 need.set(ch, need.get(ch) - 1);
17 }
18
19 while (missing === 0) {
20 if (right - left + 1 < minLen) {
21 minLen = right - left + 1;
22 start = left;
23 }
24 const leftCh = s[left];
25 if (need.has(leftCh)) {
26 need.set(leftCh, need.get(leftCh) + 1);
27 if (need.get(leftCh) > 0) missing++;
28 }
29 left++;
30 }
31 }
32
33 return minLen === Infinity ? '' : s.slice(start, start + minLen);
34}
效果图
当前场景
need
A: 1B: 1C: 1
第 1 / 28 步