76. 最小覆盖子串

• 题目
• 解题思路
• 代码

题目

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

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

解题思路

主要搞清楚增大窗口，直至包含T中所有字符后停下来，然后不断收缩窗口，直到窗口中的字符串不再满足要求。然后重复上面的两个步骤即可。

其实还是只要套模板，具体思路见书87面

代码

class Solution {
    public String minWindow(String s, String t) {
        //存放我们需要的字串的字符，以及他们的个数，比如t为“ABC”，那么need{A:1,B:1,C:1}
        Map<Character, Integer> need = new HashMap<>();
        //滑动窗口
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            //取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        int valid = 0;//窗口中已经满足need中条件的字符个数。比如窗口已经有一个A了，那么valid=1

        // 记录最小覆盖字串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            //c：即将移入窗口的字符
            char c = s.charAt(right);
            //右移窗口
            right++;
            //进行窗口内一系列数据的更新
            if (need.containsKey(c)) {
                //把C移入窗口，同时记录该字符出现的次数
                window.put(c, window.getOrDefault(c, 0) + 1);
                //如果该字符已经达到了need的要求，就可以把valid+1了。
                /*
                    最后一个测试用例一直过不了，因为定义的Map的value类型为Integer是对象，
                    Integer会缓存频繁使用的数值[-128,127]，超过此范围就会new一个对象，
                    导致使用“==”错误，改为equals()即可。
                */
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            //判断左侧窗口是否需要收缩
            //本题中收缩的条件是窗口中的字符已经符合了要求
            while (valid == need.size()) {//需要的字符个数已经全部满足了
                if (right - left < len) {//right - left：当前窗口的长度
                    start = left;
                    len = right - left;
                }

                //d是即将移出窗口的字符
                char d = s.charAt(left);
                //收缩窗口左边界
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;//合适的字符减少了一种
                    }
                    //在window中也要将该字符出现的次数减少1
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }


        //如果len没动过，证明不能满足题目的条件，如果动过，证明可以满足，截取出来该字串即可
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}