Q：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
A：引用：《labuladong的算法小抄》
使用滑动窗口。滑动窗⼝算法的思路是这样：
1、我们在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right =0，把索引闭区间 [left, right] 称为⼀个「窗⼝」。
2、我们先不断地增加 right 指针扩⼤窗⼝ [left, right]，直到窗⼝中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left,right]，直到窗⼝中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新⼀轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
下⾯画图理解⼀下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和窗⼝中的相应字符的出现次数。
初始状态：
增加 right，直到窗⼝ [left, right] 包含了 T 中所有字符：
现在开始增加 left，缩⼩窗⼝ [left, right]。
直到窗⼝中的字符串不再符合要求，left 不再继续移动。
之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
代码：
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0)
return "";
int left = 0, right = 0;
int start = 0, minLen = Integer.MAX_VALUE;
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> need = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char temp = t.charAt(i);
if (need.containsKey(temp))
need.put(temp, need.get(temp) + 1);
else
need.put(temp, 1);
}
int match = 0;
while (right < s.length()) {
char now = s.charAt(right);
if (need.containsKey(now)) {
if (window.containsKey(now)) {
window.put(now, window.get(now) + 1);
} else {
window.put(now, 1);
}
if (window.get(now).equals(need.get(now))) {
//字符now的出现次数符合要求了
match++;
}
}
//window中的字符串符合need的要求了
while (match == need.size()) {
if (right - left < minLen) {
start = left;
minLen = right - left + 1;
}
char temp = s.charAt(left);
if (window.containsKey(temp)) {
//temp移出去
window.put(temp, window.get(temp) - 1);
if (window.get(temp) < need.get(temp)) {
//temp出现次数不再符合要求
match--;
}
}
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}