力扣HOT100 - 76. 最小覆盖子串

解题思路：

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length())
            return "";
        Map<Character, Integer> tmap = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
 
        // 记录 t 中每个字符的出现次数
        for (char c : t.toCharArray())
            tmap.put(c, tmap.getOrDefault(c, 0) + 1);
 
        int left = 0, right = 0;// 窗口的左右边界
        int valid = 0;// 已经匹配上的字符数量
        int start = 0, minLen = Integer.MAX_VALUE;// 最小窗口的起始位置和长度
 
        while (right < s.length()) {
            char r = s.charAt(right);
            right++;
            if (tmap.containsKey(r)) {
                window.put(r, window.getOrDefault(r, 0) + 1);
                //不能用==，window.get(r) 和 tmap.get(r) 都返回的是 Integer 类型的对象。当使用 == 进行比较时，实际上比较的是两个 Integer 对象的引用，而非它们的值。
                if (window.get(r).equals(tmap.get(r)))
                    valid++;
            }
            while (valid == tmap.size()) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char l = s.charAt(left);
                if (tmap.containsKey(l)) {
                    window.put(l, window.get(l) - 1);
                    if (window.get(l) < tmap.get(l))
                        valid--;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}