最小覆盖子串怎么用滑动窗口解？如何判断窗口已覆盖目标？

简化版

在字符串 s 里找包含 t 所有字符(含重复次数)的最短子串。用求最短滑动窗口 + 计数:need 记录 t 里每个字符要多少个,window 记录窗口里的计数,用一个 valid 变量记「已满足数量要求的字符种类数」。right 扩展直到 valid == need 的种类数(已覆盖),然后收缩 left 求最短,同时维护 valid。O(|s| + |t|)。这是「求最短」滑窗的经典难题。

详细版

String minWindow(String s, String t) {
    Map<Character,Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int left = 0, valid = 0;                 // valid: 已满足要求的字符种类数
    int start = 0, len = Integer.MAX_VALUE;  // 记录最短窗口
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++; // c 数量刚好满足
        }
        while (valid == need.size()) {        // 窗口已覆盖 t → 收缩求最短
            if (right - left + 1 < len) {      // 更新最短
                start = left; len = right - left + 1;
            }
            char d = s.charAt(left);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--; // 移出后不再满足
                window.merge(d, -1, Integer::sum);
            }
            left++;
        }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

完整版教学

一、为什么是「求最短」滑动窗口

题目要「最短的、覆盖 t 所有字符的子串」,是典型求最短滑窗。策略和「求最长」相反:right 先扩展到窗口满足条件(覆盖了 t),然后在满足条件的前提下拼命收缩 left 求最短,直到不再满足才停,再继续扩 right。对照模板,它属于「合法就收缩、收缩时更新 min」这一类。难点在于「如何高效判断窗口已经覆盖了 t」。

二、覆盖判断:need / window / valid 三件套

判断「窗口是否包含 t 的所有字符(含重复次数)」如果每次都比较两个哈希表,太慢。用一个巧妙的计数机制:

need:t 中每个字符需要的数量(need['A']=1 表示要 1 个 A)。
window:当前窗口中每个(t 需要的)字符的数量。
valid:已经「数量达标」的字符种类数。当某字符在窗口里的数量恰好等于 need 的要求时,valid++。

当 valid == need.size()(所有种类都达标)时,窗口就完整覆盖了 t。用一个整数 valid 代替「每次比较整个哈希表」,把判断降到 O(1)。

三、valid 的增减时机(关键细节)

valid 的维护要精确,是本题最易错处:

加入字符时:window[c]++ 后,只有当 window[c] 恰好等于 need[c] 时才 valid++。注意是「恰好等于」——超过了不再增加 valid(多余的字符不影响「达标」判断)。
移出字符时:先判断「移出前是否恰好达标」——如果 window[d] == need[d](移出后就不达标了),先 valid--,再 window[d]--。顺序不能反。

这个「恰好相等才增减 valid」的逻辑,保证了 valid 精确反映「有多少种字符数量达标」。

四、走一遍流程

s = "ADOBECODEBANC", t = "ABC"
need = {A:1, B:1, C:1}
right 扩展到 "ADOBEC"：valid=3（A,B,C都齐）→ 进入收缩
  收缩 left："DOBEC"...直到不满足，记录最短候选 "ADOBEC"(6)
继续 right 扩展、遇满足再收缩...
最终最短是 "BANC"(4)

right 扩到覆盖,left 收到极限,交替进行,记录过程中最短的窗口。

五、为什么复杂度是 O(|s| + |t|)

初始化 need 遍历 t:O(|t|)。
主循环:right 遍历 s 一遍,left 最多也遍历 s 一遍(每个字符进出窗口各一次),O(|s|)。
valid 的维护和窗口判断都是 O(1)。
总计 O(|s| + |t|),空间 O(字符集)。

关键是用 valid 把「判断是否覆盖」从 O(字符集) 降到 O(1),否则每步比较哈希表会退化。

六、和「求最长」题的对比

无重复最长子串(求最长):窗口不合法(有重复)才收缩,合法时更新 max。
最小覆盖子串(求最短):窗口合法(已覆盖)就收缩,收缩时更新 min。

两者是滑动窗口的两个方向,收缩条件和更新时机正好相反。掌握这一对,滑动窗口的两大类题就都通了。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：window 覆盖 need 且 valid 等于所需不同字符数时，当前窗口才合法。

对应的状态推进是：右扩更新计数与 valid，合法后左缩并在破坏覆盖前更新答案。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。s 与 t 中字符各被线性处理，时间 O(|s|+|t|)。

带数字走一遍：s=ADOBECODEBANC、t=ABC 的最小覆盖为 BANC。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	字符数量必须按频次而非仅按集合判断
时间复杂度	O(
额外空间	O(字符集大小)
关键边界	valid 只在计数从 need-1 到 need 或从 need 到 need-1 时变化
替代方案	若字符集固定可用数组计数，通用字符用 Map

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“字符数量必须按频次而非仅按集合判断”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(|s|+|t|) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“s 与 t 中字符各被线性处理，时间 O(|s|+|t|)”。
误区：重复值和边界值不会改变代码。 valid 只在计数从 need-1 到 need 或从 need 到 need-1 时变化。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“window 覆盖 need 且 valid 等于所需不同字符数时，当前窗口才合法”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“s=ADOBECODEBANC、t=ABC 的最小覆盖为 BANC”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“若字符集固定可用数组计数，通用字符用 Map”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

最小覆盖子串 = 求最短滑动窗口 + 计数:need(t 各字符需求量)、window(窗口内计数)、valid(已达标的字符种类数)。right 扩展,某字符 window[c] 恰好等于 need[c] 时 valid++;valid == need.size() 即已覆盖,收缩 left 求最短(移出前若 window[d]==need[d] 先 valid--)。用 valid 把覆盖判断降到 O(1),总 O(|s|+|t|)。和「求最长」相反:合法就缩、缩时更新 min。

简化版

详细版