76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

本题是标准的滑动窗口，一个左指针，一个右指针，先滑动右指针，当左右指针内的字母包含了所有T那就记录下来，这是一个答案，然后滑动左指针直到左右指针内的字母没有包含所有T字母，每一次遍历都需要记录下来答案，然后继续滑动右指针即可。
思路其实并不复杂，但是如何简化，就需要好好考虑了，我这里采用的是哈希表，先将所有T字母出现次数储存下来，然后再用另一个表储存左右指针内的S字符出现次数，当出现一个字符出现的次数相同就让一个变量匹配值加一，直到整个变量等于T字符的哈希表的大小，将其记录下来。

• 注意1：在代码中，当match == size 一定要立即判断，使用while循环，如果用if else 的话那当right遍历到最后一个字母时，就会直接出循环，不会在进行缩短字符串的操作了。
• 注意2: 在代码中，Integer的自动装箱我们用equal来判等，直接用==会出错，原因在于缓冲池。

代码如下:

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0)
            return "";
        HashMap <Character,Integer> tMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);
            tMap.put(ch,tMap.getOrDefault(ch,0)+1);
        }
        
        HashMap<Character,Integer> sMap = new HashMap<>();
        int[] ans = new int[]{Integer.MAX_VALUE,0,0};
        int match = 0;

        int left = 0,right = 0;
        int size = tMap.size();
        while(right < s.length()){
            if (match < size){
                char ch = s.charAt(right);
                if ( tMap.containsKey(ch)){
                    sMap.put(ch,sMap.getOrDefault(ch,0)+1);
                    if (sMap.get(ch).equals(tMap.get(ch))){
                        match++;
                    }
                }
                right++;
            }
            while (match == size) {
                int len = right - left;
                if (ans[0] > len){
                    ans[0] = len;
                    ans[1] = left;
                    ans[2] = right;
                }
                char ch = s.charAt(left);
                if (tMap.containsKey(ch)){
                    if (sMap.get(ch).equals(tMap.get(ch))){
                        match--;
                    }
                    sMap.put(ch,sMap.get(ch)-1);
                }
                left++;
            }

        }
        String res = "";
        if (ans[0] == Integer.MAX_VALUE) return res;
        res = s.substring(ans[1],ans[2]);
        return res;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。