Minimum Window Substring 是 LeetCode Hot 100 里面一道非常经典的滑动窗口题。
这道题之所以经典，是因为它几乎把滑动窗口的核心思想完整体现出来了：
-
什么时候扩张右边界
-
什么时候收缩左边界
-
-
如何在满足条件的前提下继续优化答案
很多人第一次做这题时，会觉得它比普通窗口题难一些。因为这道题不是简单地求“最长”或者“固定长度”，而是要求：
找到一个最短的子串，使它包含字符串 t 中所有字符。
这意味着窗口不仅要“覆盖”，还要“尽量短”。 所以它不是单纯地滑过去，而是要在“扩张”和“收缩”之间不断切换。
你给出的这份 Java 代码，使用的是这道题非常标准的一种写法：
双哈希表 + 滑动窗口
这种写法的核心思路非常清晰：
-
用一个哈希表统计
t中每个字符需要多少个 -
再用另一个哈希表维护当前窗口中这些字符出现了多少次
-
当窗口已经覆盖
t后，开始尽可能缩小窗口 -
在缩小过程中不断更新最短答案
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定两个字符串 s 和 t，要求你在 s 中找到一个最短子串，使得这个子串包含 t 中所有字符。
这里的“包含”有两个要点：
-
不只是字符种类要包含
-
字符出现次数也必须满足
例如：
s = "ADOBECODEBANC"
t = "ABC"
那么答案是：
"BANC"
因为：
-
"BANC"中包含A、B、C -
并且它已经是所有满足条件子串里最短的一个
如果不存在这样的子串，就返回空字符串。
示例
示例 1
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2
输入：s = "a", t = "a"
输出："a"
因为整个字符串本身就已经满足要求。
示例 3
输入：s = "a", t = "aa"
输出：""
因为 s 中只有一个 a，无法覆盖两个 a，所以返回空串。
最直接的想法为什么不好？
如果不考虑优化，一个很自然的思路可能是：
-
枚举
s的所有子串 -
对每个子串统计字符频率
-
看它是否覆盖
t -
记录其中最短的那个
这个方法理论上能做出来，但效率非常低。
假设 s 的长度是 n：
-
子串数量大约是
O(n^2) -
每个子串再去统计判断，代价还很高
总复杂度会非常难看，肯定不能作为这道题的高效解法。
所以这题真正适合的思路，是：
用一个动态变化的窗口，在扫描过程中维护覆盖关系。
这就是滑动窗口。
核心思路：滑动窗口
这道题最关键的观察是：
我们要找的是一个连续子串，而且这个子串需要满足“包含 t 所有字符”的条件。 这正是滑动窗口特别擅长处理的场景。
窗口怎么工作？
我们用两个指针：
-
lef：窗口左边界 -
rig：窗口右边界
窗口表示的就是：
s[lef ... rig-1]
基本流程
-
不断移动右指针，让窗口逐渐变大
-
一旦窗口已经满足覆盖
t的条件，就尝试移动左指针缩小窗口 -
在缩小过程中更新最短答案
-
如果缩小到不再满足条件，就继续扩张右边界
这就是这道题滑动窗口的完整节奏：
先扩张找到可行解，再收缩逼近最优解。
你的代码在做什么？
你这段代码用了两个哈希表：
bucket1
记录字符串 t 中每个字符需要的数量。
例如：
t = "AABC"
那么：
bucket1 = {
A: 2,
B: 1,
C: 1
}
bucket2
记录当前窗口中，这些目标字符已经出现了多少次。
同时你还用了一个变量：
num
表示当前有多少种字符已经“满足要求”。
也就是说，当某个字符在窗口中的数量 刚好达到 bucket1 里的要求时，就让 num++。
当：
num == bucket1.size()
时，说明当前窗口已经覆盖了 t 的所有字符。
这时候就可以开始尝试收缩左边界。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public String minWindow(String s, String t) {
StringBuilder res = new StringBuilder();
// bucket1: 记录 t 中每个字符需要的数量
HashMap<Character, Integer> bucket1 = new HashMap<>();
// bucket2: 记录当前窗口中目标字符的出现次数
HashMap<Character, Integer> bucket2 = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
bucket1.put(t.charAt(i), bucket1.getOrDefault(t.charAt(i), 0) + 1);
}
int lef = 0, rig = 0;
// num 表示当前已经满足要求的字符种类数
int num = 0;
int ansLength = s.length() + 1;
int ansLef = 0, ansRig = 0;
while (rig < s.length()) {
char nowPos = s.charAt(rig);
rig++;
// 如果当前字符属于目标字符，就更新窗口统计
if (bucket1.getOrDefault(nowPos, 0) != 0) {
bucket2.put(nowPos, bucket2.getOrDefault(nowPos, 0) + 1);
// 如果该字符数量刚好达到要求，满足种类数 +1
if (bucket2.get(nowPos).equals(bucket1.get(nowPos))) num++;
}
// 当窗口已经覆盖所有目标字符时，尝试收缩左边界
while (num == bucket1.size()) {
if (rig - lef < ansLength) {
ansLef = lef;
ansRig = rig;
ansLength = rig - lef;
}
char pushPos = s.charAt(lef);
lef++;
if (bucket1.containsKey(pushPos)) {
bucket2.put(pushPos, bucket2.get(pushPos) - 1);
// 如果收缩后某个字符不再满足要求，就退出收缩阶段
if (bucket2.get(pushPos) < bucket1.get(pushPos)) num--;
}
}
}
if (ansLength == s.length() + 1) return res.toString();
for (int i = ansLef; i < ansRig; i++) res.append(s.charAt(i));
return res.toString();
}
}
代码拆解
这段代码不算短，但如果把每个变量的角色理清楚，整体逻辑其实非常顺。 下面一步一步来看。
1. 为什么要先统计 t 的字符频率？
for (int i = 0; i < t.length(); i++) {
bucket1.put(t.charAt(i), bucket1.getOrDefault(t.charAt(i), 0) + 1);
}
因为题目要求窗口必须覆盖 t 的所有字符，而且字符数量也要够。
所以首先必须知道：
-
t里有哪些字符 -
每个字符需要多少个
这就是 bucket1 的作用。
例如：
t = "AABC"
则：
A 需要 2 个
B 需要 1 个
C 需要 1 个
如果不先把这个“目标条件”保存下来，后面就没法判断窗口是否合格。
2. 为什么窗口是 [lef, rig) 这种写法？
代码里你是这样更新右边界的：
char nowPos = s.charAt(rig);
rig++;
这说明窗口表示的是：
[lef, rig)
也就是左闭右开区间。
这种写法的好处是：
-
当前窗口长度可以直接写成：
rig - lef
-
截取子串时边界也更自然
这是滑动窗口里非常常见的一种实现方式。
3. 为什么只有当字符在 bucket1 中时才更新 bucket2？
if (bucket1.getOrDefault(nowPos, 0) != 0) {
...
}
因为题目只关心 t 中出现过的字符。
如果当前右边加入的字符根本不在 t 里，比如：
-
t = "ABC" -
当前字符是
X
那这个字符对于“是否覆盖 t”没有任何帮助。 所以没必要在 bucket2 里记录它。
这一步相当于过滤掉所有无关字符，只专注维护目标字符的统计信息。
4. 为什么 num 表示“满足要求的字符种类数”？
if (bucket2.get(nowPos).equals(bucket1.get(nowPos))) num++;
这里的逻辑非常重要。
num 不是表示当前窗口中一共有多少个目标字符，而是表示：
当前有多少种字符已经达到了要求数量。
例如：
t = "AABC"
那么总共有 3 种字符要满足：
-
A -
B -
C
只有当：
-
A的数量至少达到 2 -
B的数量至少达到 1 -
C的数量至少达到 1
窗口才算真正覆盖 t。
所以 num == bucket1.size() 的时候，说明所有种类都已经满足要求了。
这是一种非常常见、也很高效的滑窗写法。
5. 为什么当 num == bucket1.size() 时就可以收缩左边界？
while (num == bucket1.size()) {
...
}
因为这表示当前窗口已经是一个“可行解”了。 既然已经可行，那下一步最自然的操作就是：
尝试把它变得更短。
而窗口变短的方法，就是不断移动左边界 lef。
在这个过程中：
-
如果删掉左边字符后，窗口仍然满足覆盖条件，那说明还可以继续缩
-
如果删掉后不满足了，那就说明刚才那个窗口已经是当前右边界下的最短可行窗口
这也是这道题最核心的滑窗节奏：
一旦满足条件，就尽可能收缩。
6. 为什么更新答案写成这样？
if (rig - lef < ansLength) {
ansLef = lef;
ansRig = rig;
ansLength = rig - lef;
}
因为窗口当前是 [lef, rig)，所以它的长度就是：
rig - lef
如果当前窗口已经满足覆盖条件，而且长度比历史最优答案更短，就更新答案边界。
这里记录的不是字符串本身，而是：
-
ansLef -
ansRig
等最后遍历结束后，再根据这两个边界把结果拼出来。
这种写法比每次都直接构造子串更高效，也更常见。
7. 为什么左边界收缩时，可能导致 num--？
if (bucket2.get(pushPos) < bucket1.get(pushPos)) num--;
因为当左边界右移时，相当于把窗口左边的字符扔掉了。
如果这个字符正好是目标字符，而且删掉之后它的数量变得 不再满足要求，那说明当前窗口已经不合格了。
例如：
t = "ABC"
当前窗口刚好有一个 A、一个 B、一个 C
如果左边界移走了唯一的那个 A，那当前窗口就不再覆盖 t 了。
这时候就必须：
num--
并停止继续收缩，让右边界重新扩张。
手动模拟一遍
我们用经典例子来走一下：
s = "ADOBECODEBANC"
t = "ABC"
目标条件
bucket1 = {A:1, B:1, C:1}
所以只要窗口中：
-
A 达标
-
B 达标
-
C 达标
就有：
num == 3
右边界不断扩张
一开始窗口不断扩大，直到遇到：
"ADOBEC"
这时候窗口里已经有了：
-
A
-
B
-
C
所以第一次满足条件。
开始收缩左边界
既然 "ADOBEC" 已经可行，就尝试缩小：
-
如果去掉左边的
A，窗口就不再满足条件 -
所以当前这个窗口就是一个候选答案
后面继续让右边界扩张，又会出现新的覆盖窗口，然后再不断收缩。
最终会找到最短可行窗口：
"BANC"
这就是答案。
为什么这个方法是正确的？
因为这道题的目标本质上是：
-
找到一个满足条件的窗口
-
并且在所有满足条件的窗口中取最短
而滑动窗口正好可以做到这两点：
右边界扩张
保证我们不会漏掉任何可能成为答案的窗口。
左边界收缩
保证一旦窗口可行，就立即向最短方向逼近。
更重要的是，在整个过程中：
-
每个字符最多被右指针访问一次
-
每个字符最多被左指针移出一次
所以不会重复做无意义的工作。
因此这种方法既正确，又高效。
复杂度分析
假设：
-
s的长度为n -
t的长度为m
时间复杂度
右指针 rig 从左到右扫描一遍，左指针 lef 也最多扫描一遍。 虽然有两层 while，但两个指针都只单调向前移动，不会回退。
所以总时间复杂度是：
O(n + m)
其中：
-
O(m)用来初始化bucket1 -
O(n)用来滑动窗口扫描s
空间复杂度
主要来自两个哈希表：
-
bucket1 -
bucket2
最坏情况下，它们记录的字符种类数与字符集大小有关。 一般可写为：
O(|字符集|)
如果按字符串长度上界来粗略写，也可以理解为：
O(m)
这道题真正想考什么？
这道题表面上是在找子串，但本质上考察的是滑动窗口的完整套路。
第一，是否能区分“扩张条件”和“收缩条件”
很多滑窗题最难的地方，其实不是代码，而是搞清楚：
-
什么情况下应该扩张右边界
-
什么情况下应该收缩左边界
这题的答案非常典型：
-
不满足条件就扩张
-
满足条件就收缩
第二，是否能设计出正确的“窗口满足条件”判断方式
这里的难点不是种类，而是数量。 所以不能只用一个 Set 判断字符是否出现过，而必须统计频次。
第三，是否能在满足条件的同时更新最优解
这题不是只问“有没有”，而是问“最短是多少”。 所以在每次窗口可行时，都要顺手更新答案。
这就是为什么它比普通滑窗题更经典。
和“无重复字符的最长子串”有什么区别？
这两题都用滑动窗口，但目标完全不同。
无重复字符的最长子串
重点是：
-
窗口内部不能有重复
-
求最长长度
最小覆盖子串
重点是：
-
窗口必须覆盖目标字符
-
求最短长度
所以一个是“满足约束下尽量长”，一个是“满足约束下尽量短”。
这也是为什么这题的收缩逻辑比普通最长子串题更关键。
总结
这道题的核心思想可以概括成一句话：
用滑动窗口维护当前子串中的字符频次，当窗口已经覆盖 t 时，尽可能收缩左边界，从而找到最短的合法窗口。
具体步骤就是：
-
用
bucket1统计t中每个字符需要的数量 -
用
bucket2统计当前窗口中的字符数量 -
右指针不断扩张窗口
-
当所有目标字符都满足要求时，尝试收缩左边界
-
在收缩过程中不断更新最短答案
-
如果窗口不再满足条件，就继续扩张右边界
这样就能在：
O(n + m)
的时间复杂度下解决问题。
这是一道非常经典、也非常值得反复理解的滑动窗口题。 因为它会让你真正体会到：
-
滑动窗口不只是“固定长度”
-
更重要的是学会动态维护窗口条件
-
“满足后收缩”是很多最优窗口题的核心套路
把这道题真正吃透之后，再去看：
-
串联所有单词的子串
-
找到字符串中所有字母异位词
-
最长重复字符替换
-
水果成篮
这些滑动窗口题时，你会明显更容易抓住套路。
