最小覆盖子串（Minimum Window Substring）
力扣第 76 题。给定字符串 s 和 t，找 s 中包含 t 所有字符的最短子串。
核心思路：滑动窗口 + 计数器
还是滑动窗口，但比上题多一个难点——需要知道窗口是否已经”覆盖”了 t 的所有字符。
关键在于设计一个 need 变量来追踪”还缺几种字符”，避免每次都遍历整个哈希表来判断是否满足条件。
最优解法：O(n) 滑动窗口
class Solution {
public:
string minWindow(string s, string t) {
int freq[128] = {}; // 记录 t 中各字符还需要多少个
for (char c : t)
freq[c]++;
int need = t.size(); // 还需要凑齐多少个字符（含重复）
int left = 0;
int ans_start = 0, ans_len = INT_MAX;
for (int right = 0; right < s.size(); right++) {
// 1. 右边字符入窗口
char rc = s[right];
if (freq[rc] > 0)
need--; // 这个字符是 t 还缺的，need--
freq[rc]--;
// 2. 窗口已覆盖 t，尝试收缩左边
while (need == 0) {
// 更新最优解
if (right - left + 1 < ans_len) {
ans_len = right - left + 1;
ans_start = left;
}
// 左边字符出窗口
char lc = s[left];
freq[lc]++;
if (freq[lc] > 0)
need++; // 这个字符重新变成缺的，need++
left++;
}
}
return ans_len == INT_MAX ? "" : s.substr(ans_start, ans_len);
}
};
理解两个关键设计
① freq 数组的含义随着窗口变化
初始时 freq[c] 是 t 中 c 的需求量。窗口右扩时 freq[rc]--，左缩时 freq[lc]++。所以它始终代表当前窗口相对于 t 的净缺口：
freq[c] > 0：窗口还欠 t 中 c 的字符freq[c] <= 0：窗口中 c 已经够了（甚至多余）
② need 是精髓
need 记录的是”还有几个字符位置未被满足”。只有当 freq[c] 从 1 变到 0（正好补上缺口）时，need-- 才有意义；从 0 变到 -1 是多余的字符，不改变 need。这样 need == 0 就精确等价于”窗口已完全覆盖 t”，判断 O(1) 完成。
完整走一遍例子
s = "ADOBECODEBANC", t = "ABC"
初始: freq = {A:1, B:1, C:1}, need = 3
right 扩张直到 need == 0（找到第一个覆盖窗口 "ADOBEC"）
→ 开始收缩 left，更新最优解
→ left 移到 'D' 时，A 从窗口移出，need 变回 1
→ right 继续扩张，找到下一个覆盖窗口 "DOBECODEBA"...
→ 最终最优解是 "BANC"，长度 4复杂度
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(n + m) | n = |s|，m = |t|，每个字符最多进出窗口各一次 |
| 空间 | O(∣Σ∣) | 字符集大小，ASCII 下固定 128 |
和上题的对比
| 最长不重复子串 | 最小覆盖子串 | |
|---|---|---|
| 窗口目标 | 无重复字符 | 覆盖 t 所有字符 |
| 收缩时机 | 有重复就收缩 | 满足条件后尽量收缩 |
| 判断条件 | 集合 contains | need == 0 |
| 求的是 | 最长 | 最短 |
三道题（接雨水、最长不重复、最小覆盖子串）连起来看，会发现双指针/滑动窗口的本质是：用单调性把 O(n²) 暴力枚举压缩成 O(n)——这是面试中最值得讲清楚的一条主线。