76. 最小覆盖子串

题目链接
注意，这个题是困难，以后困难题少花时间

分析

子串其实就是子数组，所以很容易想到滑动窗口，滑动窗口的解题框架如下，

什么时候移动快指针：不满足条件就移动快指针
什么时候移动慢指针：满足条件就移动慢指针，同时记录下最小长度，并记录下此时的慢指针，这样就能输出最后的字符串
什么时候跳出循环：需要移动快指针，而快指针已经到数组的最后一个元素的时候，就可以直接退出了。
然后因为本题是求最小值，因此就在移动慢指针的时候更新结果。
那核心问题就是，如何判断当前子串满足条件，即如何快速判断一个子串包含目标字符串的所有字符。
首先想到的方法是，先统计目标字符串的所有字符串及其出现次数（我们甚至可以直接用 HashMap 来保存），然后再进行双指针移动的时候，记录并更新双指针确定的子数组中所有字符的出现次数 sourceCount，每移动一次就有目标字符串中的字符以及其个数对比一次，但是这样，每次对比都得循环目标字符串的所有字符。
有没有更高效的办法呢？有！
我们除了记录子字符串中的所有字符的个数之外，还额外使用一个变量，这个变量的作用是记录目标字符串中的字符，在当前子数组中的出现个数 count，规则如下
只有字符在当前子数组中出现的次数小于在目标字符串中出现的次数的时候，才累加这个变量，如果等于，再累加也没有意义。
当我们移动慢指针的时候，移动之前，慢指针指向的字符在当前子数组中出现的次数小于等于在目标字符串中出现的次数的时候，才减少这个变量。现在等于，移除之后就小于了，所以等于的时候也递减。
这样，每次移动指针的时候，只要观察这个变量，我们就能知道当前子数组是否完全包含一个字符串的所有字符。
我们要非常注意这个 count 变量跟 sourceCount 的更新方式的不同，
count，不会超过目标字符串的长度
sourceCount：实际有多少个字符，就是多少个，可能会超过同一个字符在目标字符串中的个数
先更新 count，再更新 sourceCount
代码如下
移动快指针

// 不在目标字符串中出现的字符不统计
if(targetCount[charFast]>0){
    // 如果子数组中，某个字符串的数量已经大于等于这个字符串在目标字符串中的数量，那count就没有再累加的必要了
    if(sourceCount[charFast]<targetCount[charFast]){
        count++;
    }
    // 判断完之后，再累加sourceCount
    sourceCount[charFast]+=1;
}

移动慢指针

// 不在目标字符串中出现的字符不统计
if(targetCount[charSlow]>0){
    // 字符在子数组中的数量小于在目标字符串中的数量，才减少count
    if(sourceCount[charSlow]<=targetCount[charSlow]){
        count--;
    }
    // 判断完之后，再累加sourceCount
    sourceCount[charSlow]-=1;
}

还有一个小技巧，小优化： ASCII 字符都有一个对应的 ASCII 码，所有 ASCII 字符有 128 个，我们可以将每一个字符的 ASCII 码当作下标，然后用下表对应的个数当作字符出现的个数，这样就可以不使用 HashMap 了。
这个其实给了我们启发，所有对字符串包含的考察，我们都可以使用这个方法。

参考哈希表就会明白：将一个字符的 ASCII 码当作下标，实际上就是一种哈希函数，key 就是字符，value 就是字符出现的次数
有一点需要注意，很反直觉，就是大写字符 A 的 ASCII 码（65）比小写字符 a 的 ASCII 码（97）要小

思路就有了
首先将目标字符串的所有字符的个数统计到一个 int[128] 的数组之中
子数组为 [slow,fast)。并且从 [0,0) 开始
开始 while 循环，并根据 count 跟目标字符串的长度判断是应该移动快指针还是慢指针

不满足条件，移动快指针：
- 判断 fast 是否到了最后一个元素，如果是，则需要跳出循环
- 更新 count 和 sourceCount
- 移动快指针
满足条件：
- 先更新结果字符串的起点和长度
- 更新 count 和 sourceCount
- 移动慢指针
  为什么在这道题里我们要在移动慢指针的时候更新结果，因为我们是用滑动窗口求满足条件最小值。
  假设 t 的长度为 n，s 的长度为 m，算法复杂度为 O(n+2m)

解题

这个题其实我一上来就有思路了，但是写的过程非常的难受，老是报错，非常复杂
有几点需要注意：
之前我都是习惯使用，[slow,fast] 例如 209. 长度最小的子数组，但是这个题不是，这个题用的是左闭右开区间 [slow,fast)，因此会出现一个极端情况，就是当遍历完数组的时候，fast==source.length，此时快指针实际上是超长了的，但是此时如果还可以收缩满指针，那么就不能直接退出，因此我们在 for 循环中不能使用 fast<source.length，这也是为什么官方题解都使用两层循环的原因，用两层循环的好处就是移动慢指针的时候不用考虑快指针的情况。
其实我发现滑动窗口的题目，用 [slow,fast) 是更普遍和更合适的。这个问题我们在 904. 水果成篮中也学习过了。

public String minWindow(String s, String t) {
    char[] targetCharArr = t.toCharArray();
    char[] sourceCharArr = s.toCharArray();
    int[] targetCount = new int[128];
    int[] sourceCount = new int[128];
    // 记录目标字符串中的字符出现次数
    for(int i=0;i<targetCharArr.length;i++){
        int charObj = targetCharArr[i];
        targetCount[charObj]++;
    }
    int count=0;
    // 子数组的不包含 fast，区间为[slow,fast)
    // 初始状态这个窗口一个元素都不包含
    int slow=0,fast=0;
    // 用于最后求结果
    int minLength = sourceCharArr.length+1;
    int startPoint = 0;
    for(;;){
        // 根据count跟targetCharArr.length的大小判断移动快指针还是慢指针
        if(count<targetCharArr.length){
	        // 需要移动快指针，但是这个时候快指针已经是最后一个元素了，可以直接退出
            if(fast==sourceCharArr.length ){
                break;
            }
            int charFast = sourceCharArr[fast];
            // 不在目标字符串中出现的字符不统计
            if(targetCount[charFast]>0){
                // 如果子数组中，某个字符串的数量已经大于等于这个字符串在目标字符串中的数量，那count就没有再累加的必要了
                if(sourceCount[charFast]<targetCount[charFast]){
                    count++;
                }
                // 判断完之后，再累加sourceCount
                sourceCount[charFast]+=1;
            }
            fast++;
        }else{
            // 计算长度
            int nowLength = fast-slow;
            if(nowLength < minLength){
	            // 记录长度的同时记录起点，方便最后返回字符串
                minLength=nowLength;
                startPoint = slow;
            }
            int charSlow = sourceCharArr[slow];
            // 不在目标字符串中出现的字符不统计
            if(targetCount[charSlow]>0){
                // 字符在子数组中的数量小于在目标字符串中的数量，才减少count
                if(sourceCount[charSlow]<=targetCount[charSlow]){
                    count--;
                }
                // 判断完之后，再累加sourceCount
                sourceCount[charSlow]-=1;
            }
            slow++;
        }
    }
    if(minLength == sourceCharArr.length+1){
        return "";
    }
    return s.substring(startPoint,startPoint+minLength);

}

有的同学会在获取最终字符串的时候，可能会直接把字符串求出来，

String result = new String(Arrays.copyOfRange(sourceArr,left,right));

不要这样做，因为直接把结果求出来会复制字符串，会产生内存复制，会拖慢算法的速度。

我第三次刷这个题的时候，调试了很久才做出来这道题。主要是两个地方没有做好，

第一个就是没有想清楚什么时候更新 sourceCount，什么时候更新 count
第二个地方就是没有想清楚什么时候跳出循环。
这两个问题都暴露出我对滑动窗口这个方法的理解的不足。

另一个版本的写法，与上面写法的不同点

直接用 Hash 表计算字符出现的个数，在这里没有 char[] 数组好用。
坚持左闭合右闭区间 [left,right]。
先计算目标字符的个数，再进行累加，这样其实更好理解
基本上也就这两个变种了。而且这个版本更接近官方答案

public String minWindow(String s, String t) {
    String result = "";
    char[] sChar = s.toCharArray();
    char[] tChar = t.toCharArray();
    if (sChar.length < tChar.length) {
        return "";
    }
    Map<Character, Integer> targetMap = new HashMap<>();
    for (int i = 0; i < tChar.length; i++) {
        int amount = targetMap.getOrDefault(tChar[i], 0);
        targetMap.put(tChar[i], amount + 1);
    }
    // 先把tChar长度的加载进去，其实也不用
    int left = 0, right = 0;
    int charNum = 0;
    Map<Character, Integer> sourceMap = new HashMap<>();
    if (targetMap.containsKey(sChar[0])) {
        sourceMap.put(sChar[0], 1);
        charNum++;
    }

    int targetNum = tChar.length;
    while (true) {
        if (charNum < targetNum) {
            if (right + 1 >= sChar.length) {
                break;
            }
            char nextChar = sChar[right + 1];
            // 不处理非目标字符
            if (targetMap.containsKey(nextChar)) {
                int amount = sourceMap.getOrDefault(nextChar, 0);
                if (targetMap.get(nextChar) > amount) {
                    // 只有不足的时候，才增加 charNum
                    charNum++;
                }
                // 这里始终累加
                sourceMap.put(nextChar, amount + 1);
            }
            right++;
        } else {
            // 先更新
            if ("".equals(result) || right - left + 1 < result.length()) {
                result = s.substring(left, right + 1);
            }
            char deleteChar = sChar[left];
            // 不处理非目标字符
            if (targetMap.containsKey(deleteChar)) {
                // 先移除，再移动
                int amount = sourceMap.getOrDefault(deleteChar, 0);
                if (targetMap.get(deleteChar) >= amount) {
                    // 相等的时候也要减，如果相等，马上就要小于了
                    charNum--;
                }
                if (amount - 1 == 0) {
                    sourceMap.remove(deleteChar);
                } else {
                    sourceMap.put(deleteChar, amount - 1);
                }
            }
            left++;
        }
    }
    return result;
}

附赠官方题解

/**  
 * 优化思路：  
 * count 表示 字符在s中出现的频次  
 * count这个概念的引入成功实现了O(1)的时间按复杂度判断窗口内的元素是否包含t中所有的元素，对于需要保证元素出现次数的题目，都可以用count这个概念  
 * 此外，其实在 s 中，有的字符我们是不关心的，我们只关心 t 中出现的字符，在遍历过程中，我们完全可以跳过没在 t 中出现过的字符，避免没必要的对比  
 * 用来了ASCII码跟数字的对应关系，直接用一个长度为128(因为ASC代码总共128位) 的 int数组存放字符出现次数，省去了使用HashMap的内存和复杂度,  
 */public static String minWindow1(String s, String t) {  
    if (s.equals("") || s.length() == 0 || t .equals("") || t.length() == 0 || s.length() < t.length()) {  
        return "";  
    }  
    //题目中说 s 和 t 由英文字母组成 ，也就是说都是ASC代码，可以直接使用数字表示，那就直接当成数组下标，省去了使用HashMap的内存和复杂度  
    //数组存放指定字符出现的次数 数组长度为128，因为ASC代码总共128位  
    int[] need = new int[128];  
    int[] have = new int[128];  
    for (int i = 0; i < t.length(); i++) {  
        // int 类型默认值是0，不需要初始化  
        need[t.charAt(i)]++;  
    }  
    //t中的字符在s中出现的频次，这是一个很重要的概念，通过这个概念，可以直接判断滑动窗口中是否已经包含了t中所有的字符，真的是太棒了！！  
    int count = 0;  
    int scopeLeft = 0;  
    String result = "";  
    for (int scopeRight = 0; scopeRight < s.length(); scopeRight++) {  
        char charRight = s.charAt(scopeRight);  
        //无关的数据直接跳过  
        //每次操作have之前，都在need中对比一遍，可以节省大量的对比操作  
        if (need[charRight] == 0) {  
            continue;  
        }  
        have[charRight]++;  
        //这一步很精髓，count的值，实际上就是已经匹配的t中的元素的个数，  
        // charRight这个元素出现了t中出现的次数（need[charRight]），count就不再增加，这个不再增加的操作太妙了  
        if (have[charRight] <= need[charRight]) {  
            // have[charRight] 的数量可能超出 need[charRight]，只是超出之后，count 不会再增加  
            count++;  
        }  
        while (count == t.length()) {  
            if (result.equals("") || scopeRight - scopeLeft + 1 < result.length()) {  
                result = s.substring(scopeLeft, scopeRight + 1);  
            }  
            char charLeft = s.charAt(scopeLeft);  
            //无关的字符，直接跳过，不需要做任何比较  
            //每次操作have之前，都在need中对比一遍，可以节省大量的对比操作  
            if (need[charLeft] == 0) {  
                scopeLeft++;  
                continue;  
            }  
            //移除 s.charAt(scopeLeft) 就会破坏条件，所以count要变  
            if (have[charLeft] == need[charLeft]) {  
                // have[charLeft] 的数量是可能超出 need[charLeft]的，只有再减少到 need[charLeft] 之后，在减少才会影响条件  
                count--;  
            }  
            have[charLeft]--;  
            scopeLeft++;  
        }  
    }  
    return result;  
}

76. 最小覆盖子串

分析

解题

相关题