leetcode原题如下：
????????
????????给你一个字符串?s?、一个字符串?t?。返回?s?中涵盖?t?所有字符的最小子串。如果?s?中不存在涵盖?t?所有字符的子串，则返回空字符串?""?。
注意：
t?中重复字符，我们寻找的子字符串中该字符数量必须不少于?t?中该字符数量。s?中存在这样的子串，我们保证它是唯一的答案。????????
如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。
官方题解：
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
Map<Character, Integer> ori = new HashMap<>();
Map<Character, Integer> cnt = new HashMap<>();
// 预处理，初始化 ori 表
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = 0;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
int required = ori.size(); // 需要匹配的字符种类数量
int formed = 0; // 已经匹配的字符种类数量
while (r < sLen) {
char c = s.charAt(r);
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
formed++;
}
while (formed == required && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
char leftChar = s.charAt(l);
cnt.put(leftChar, cnt.get(leftChar) - 1);
if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
formed--;
}
l++;
}
r++;
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。
public class MinimumWindowSubstring {
public String minWindow(String s, String t) {
// 用于记录 t 中各字符需要匹配的次数
Map<Character, Integer> ori = new HashMap<>();
// 用于记录当前窗口中各字符已匹配的次数
Map<Character, Integer> cnt = new HashMap<>();
// 预处理，初始化 ori 表
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = 0; // 窗口的左右边界
int len = Integer.MAX_VALUE; // 记录当前最小窗口的长度
int ansL = -1, ansR = -1; // 记录当前最小窗口的左右边界
int sLen = s.length(); // 字符串 s 的长度
int required = ori.size(); // 需要匹配的字符种类数量
int formed = 0; // 已经匹配的字符种类数量
// 右指针滑动
while (r < sLen) {
char c = s.charAt(r);
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
// 如果当前字符在 ori 表中，并且已匹配次数等于 ori 表中的次数，增加已匹配字符种类数量
if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
formed++;
}
// 左指针滑动，窗口收缩
while (formed == required && l <= r) {
// 更新最小窗口的长度和边界
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
// 移动左指针，减少已匹配字符的次数
char leftChar = s.charAt(l);
cnt.put(leftChar, cnt.get(leftChar) - 1);
// 如果左边界字符在 ori 表中，并且减少后的次数小于 ori 表中的次数，减少已匹配字符种类数量
if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
formed--;
}
l++;
}
// 右指针继续滑动
r++;
}
// 返回最小窗口对应的子串
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
}这段代码中的核心思想是使用滑动窗口来找到包含字符串 t 中所有字符的最小窗口。下面是代码中各部分的解释：
ori 和 cnt 的初始化：
ori 表用于记录字符串 t 中各字符需要匹配的次数。cnt 表用于记录当前窗口中各字符已匹配的次数。预处理，初始化 ori 表：
t，将其中各字符及其需要匹配的次数记录在 ori 表中。窗口的左右边界 l 和 r：
l 和 r 来确定窗口。required 和 formed：
required 记录需要匹配的字符种类数量，即 ori 表的大小。formed 记录已经匹配的字符种类数量，初始为 0。右指针滑动（while (r < sLen)）：
r，直到窗口包含了字符串 s 中的所有字符。左指针滑动，窗口收缩（while (formed == required && l <= r)）：
l，尝试缩小窗口的大小。