給你一個(gè)字符串s、一個(gè)字符串t。返回s中涵蓋t所有字符的最小子串。如果s中不存在涵蓋t所有字符的子串，則返回空字符串""。

注意：如果s中存在這樣的子串，我們保證它是唯一的答案。

示例 1：

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

輸出："BANC"

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

輸出："a"

這題讓求的是s中能覆蓋t的最小子串，看到這題首先想到的就是滑動(dòng)窗口。使用兩個(gè)指針一個(gè)left，一個(gè)right，分別表示窗口的左邊界和右邊界。

• 當(dāng)窗口內(nèi)的所有字符不能覆蓋t的時(shí)候，要擴(kuò)大窗口，也就是right往右移。

• 當(dāng)窗口內(nèi)的所有字符可以覆蓋t的時(shí)候，記錄窗口的起始位置以及窗口的長度，然后縮小窗口（因?yàn)檫@里求的是能覆蓋的最小子串），left往右移。如果縮小的窗口還能覆蓋t，保存長度最小的窗口即可。

• 重復(fù)上面的操作，直到窗口的右邊不能再移動(dòng)為止。

這里我以示例1為例做個(gè)視頻，來看一下具體操作過程，加深一下理解。（如果看不清，可以切換橫向全屏觀看）

 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中字符全部覆蓋了，如果覆蓋了，要移動(dòng)窗口的左邊界
25        //找到最小的能全部覆蓋的窗口
26        while (check(map)) {
27            //如果現(xiàn)在窗口比之前保存的還要小，就更新窗口的長度
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是可以為負(fù)數(shù)的，為負(fù)數(shù)的情況就是，相同的字符右
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中每個(gè)字符的數(shù)量
 4    for (char ch : t.toCharArray())
 5        map[ch]++;
 6    //字符串t的數(shù)量
 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}

滑動(dòng)窗口類型的題也是最常見的，一般會(huì)有兩個(gè)指針，分別指向窗口的左邊界和右邊界，如果窗口不滿足條件我們就移動(dòng)右邊界來擴(kuò)大窗口，如果滿足條件我們可以移動(dòng)左邊界來縮小窗口，確定這個(gè)更小的窗口是否還滿足條件……