leetcode 76. 最小覆盖子串

用滑动窗口来解答此题，有几个关键点：

一、确认整个遍历操作中我们需要用到的变量

• left、right 就不用说了，在滑动窗口类的题目这两个变量基本必有；
• needs 哈希桶，用来表示目标字符串的各个字符以及各个字符要求出现的次数；
• windows 哈希桶，用来表示当前窗口中符合的字符，以及字符出现次数；
• start、len 分别用来实时标记最小子串的开始索引，以及其长度；
• validCount 用来记录当前窗口中满足”目标字符串字符出现的次数”的个数（有点绕。。书面表达是个硬伤T T）

二、确定左边窗口何时向右收敛

• 答案就是在右边窗口挪动时找到一对符合要求的子串时，就需要通过移动左边窗口，来尝试获取长度更小的符合要求的子串。

三、各个变量在何时被维护？仔细想想，有几个关键时刻：

1、右边窗口往右滑动：

• 如果碰到了目标字符串中的字符，我们需要维护什么变量？主要就是要维护当前窗口目标字符hash桶中的计数器；
• 如果碰到了目标字符串中的字符，而且在维护完hash桶计数器后，发现与目标字符要求出现次数相同，那么我们就认为有一个目标字符满足了出现次数的要求，让validCount加1。

2、每次窗口中字符满足覆盖要求时：

• 试算一下当前窗口的长度是否比以往更小，是则需要更新最小子串的开始索引以及其长度；
• 同时，虽然本次窗口中的字符已经满足覆盖要求，但如果我们把左边窗口往右边收敛，是不是有可能获取到一个更短但也满足覆盖要求的子串？所以我们就尝试左边窗口向右收敛；
• 在向右收敛的过程中，如果（条件1 ）本次剔除的最左边的字符刚好是目标字符串中的字符，我们就再判断下是不是（条件2）失去这个字符后不再满足覆盖要求，如果条件1与2都符合的话就要让validCount减1，而不管符不符合条件2，只要满足条件1我们都要让当前窗口字符对应的计数器减1。

最终返回目标子串即可。

某一时刻的窗口快照.png

代码实现如下：

public class Solution {

    public String minWindow(String s, String t) {
        // 用以记录需要的字符以及每个字符应该出现次数
        Map<Character, Integer> needs = new HashMap<>();
        for(int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }
        // 用以记录当前窗口中符合needs的字符以及每个字符出现的次数
        Map<Character, Integer> windows = new HashMap<>();
        // 滑动窗口的左右窗口，左闭右开[left,right)
        int left = 0, right = 0;
        // 用来记录结果：子串的开始索引以及长度
        int start = 0, len = Integer.MAX_VALUE;
        // 记录当前窗口中字符出现次数满足needs要求的个数，只有当全部字符出现个数都满足了，左窗口才尝试向右收缩
        int validCount = 0;
        while (right < s.length()) {
            // 往右滑动
            char c = s.charAt(right++);
            // 找到一个需要的字符
            if (needs.containsKey(c)) {
                // 当前窗口统计该字符的hash桶计数器+1
                windows.put(c, windows.getOrDefault(c, 0) + 1);
                // 出现的次数刚好达到要求
                if (windows.get(c).equals(needs.get(c))) {
                    // 表示当前窗口中，当前字符的出现次数已达到要求
                    validCount++;
                }
            }

            // 所有字符的出现字数都满足了，那么准备左边窗口向前收缩（尝试圈一个更小的子串）
            while (validCount == needs.size()) {
                // 每次达到字符数要求，就试图更新一下字串开始索引与长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 左边窗口向前收缩
                char l = s.charAt(left++);
                // 如果收缩前最左边的字符为需要的字符，那么更新当前窗口完成的字符个数，并更新窗口中有效字符个数
                if (needs.containsKey(l)) {
                    // 右移去掉该字符后，出现次数达不到要求，那么符合needs要求的个数要减1
                    if (windows.get(l).equals(needs.get(l))) {
                        validCount--;
                    }
                    windows.put(l, windows.get(l) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

}