给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。

注意：如果s中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

输入：s = "a", t = "a"

输出："a"

这题让求的是s中能覆盖t的最小子串，看到这题首先想到的就是滑动窗口。使用两个指针一个left，一个right，分别表示窗口的左边界和右边界。

• 当窗口内的所有字符不能覆盖t的时候，要扩大窗口，也就是right往右移。

• 当窗口内的所有字符可以覆盖t的时候，记录窗口的起始位置以及窗口的长度，然后缩小窗口（因为这里求的是能覆盖的最小子串），left往右移。如果缩小的窗口还能覆盖t，保存长度最小的窗口即可。

• 重复上面的操作，直到窗口的右边不能再移动为止。

这里我以示例1为例做个视频，来看一下具体操作过程，加深一下理解。（如果看不清，可以切换横向全屏观看）

 1public String minWindow(String s, String t) {
 2    //把t中的字符全部放到map中
 3    Map<Character, Integer> map = new HashMap<>();
 4    for (char ch : t.toCharArray())
 5        map.put(ch, map.getOrDefault(ch, 0) + 1);
 6
 7    int left = 0;//窗口的左边界
 8    int right = 0;//窗口的右边界
 9
10    //满足条件的窗口开始位置
11    int strStart = 0;
12    //满足条件的窗口的长度
13    int windowLength = Integer.MAX_VALUE;
14
15    while (right < s.length()) {
16        //记录右指针扫描过的字符
17        char rightChar = s.charAt(right);
18        //如果右指针扫描的字符存在于map中，就减1
19        if (map.containsKey(rightChar))
20            map.put(rightChar, map.getOrDefault(rightChar, 0) - 1);
21        //记录之后右指针要往右移
22        right++;
23
24        //检查窗口是否把t中字符全部覆盖了，如果覆盖了，要移动窗口的左边界
25        //找到最小的能全部覆盖的窗口
26        while (check(map)) {
27            //如果现在窗口比之前保存的还要小，就更新窗口的长度
28            //以及窗口的起始位置
29            if (right - left < windowLength) {
30                windowLength = right - left;
31                strStart = left;
32            }
33            //移除窗口最左边的元素，也就是缩小窗口
34            char leftChar = s.charAt(left);
35            if (map.containsKey(leftChar))
36                map.put(leftChar, map.getOrDefault(leftChar, 0) + 1);
37            //左指针往右移
38            left++;
39        }
40    }
41    //如果找到合适的窗口就截取，否则就返回空
42    if (windowLength != Integer.MAX_VALUE)
43        return s.substring(strStart, strStart + windowLength);
44    return "";
45}
46
47//检查窗口是否把字符串t中的所有字符都覆盖了，如果map中所有
48// value的值都不大于0，则表示全部覆盖
49private boolean check(Map<Character, Integer> map) {
50    for (int value : map.values()) {
51        //注意这里的value是可以为负数的，为负数的情况就是，相同的字符右
52        // 指针扫描的要比t中的多，比如t是"ABC"，窗口中的字符是"ABBC"
53        if (value > 0)
54            return false;
55    }
56    return true;
57}

 1public String minWindow(String s, String t) {
 2    int[] map = new int[128];
 3    //记录字符串t中每个字符的数量
 4    for (char ch : t.toCharArray())
 5        map[ch]++;
 6    //字符串t的数量
 7    int count = t.length();
 8    int left = 0;//窗口的左边界
 9    int right = 0;//窗口的右边界
10    //覆盖t的最小长度
11    int windowLength = Integer.MAX_VALUE;
12    //覆盖字符串t开始的位置
13    int strStart = 0;
14    while (right < s.length()) {
15        if (map[s.charAt(right++)]-- > 0)
16            count--;
17        //如果全部覆盖
18        while (count == 0) {
19            //如果有更小的窗口就记录更小的窗口
20            if (right - left < windowLength) {
21                windowLength = right - left;
22                strStart = left;
23            }
24            if (map[s.charAt(left++)]++ == 0)
25                count++;
26        }
27    }
28    //如果找到合适的窗口就截取，否则就返回空
29    if (windowLength != Integer.MAX_VALUE)
30        return s.substring(strStart, strStart + windowLength);
31    return "";
32}

滑动窗口类型的题也是最常见的，一般会有两个指针，分别指向窗口的左边界和右边界，如果窗口不满足条件我们就移动右边界来扩大窗口，如果满足条件我们可以移动左边界来缩小窗口，确定这个更小的窗口是否还满足条件……