leetcode 76. 最小覆盖子串

代码：

class Solution {
    public String minWindow(String ss, String tt) {
        char[]s=ss.toCharArray();
        char[]t=tt.toCharArray();

        int[] hash1=new int[128];   //用数组代替哈希表存储 t 字符串中字符对应的个数
        for(char ch:t){
            hash1[ch]++;
        }

        int[]hash2=new int[128];    //用数组代替哈希表存储讨论的子串中字符对应的个数

        int count=0;    //记录子串中有效字符的个数

        int minLeft=-1;  //最短子串的起始下标
        int minLength=Integer.MAX_VALUE;

        for(int left=0,right=0;right<s.length;right++){
            //把 right 指向的字符入窗口
            char in=s[right];
            hash2[in]++;

            //判断入窗口的字符是否是有效字符
            if(hash2[in]<=hash1[in]){
                count++;
            }

            //判断当前讨论的子串是否符合要求(是否含有 t 字符串中的所有字符，是否是最短子串)
            while (count==t.length){
                //判断当前子串是否最短
                if(right-left+1<minLength){
                    minLength=right-left+1;
                    minLeft=left;
                }
                //以 left 指针为首的子串讨论完毕
                //出窗口
                char out=s[left];
                //判断出窗口的字符是否是有效字符
                if(hash2[out]<=hash1[out]){
                    count--;
                }
                hash2[out]--;
                left++;
            }

        }

        if(minLeft==-1){
            return "";
        }else {
            return ss.substring(minLeft,minLeft+minLength);
        }
    }
}

题解：

? ? ? ? 本题的题意很清晰，要求我们在字符串 s 中找到含有 t 字符串中所有字符的最小子串

? ? ? ? 我们首先可以想到一个暴力解法：遍历出字符串 s 中的所有子串，找到符合条件含有 t 字符串中所有字符的子串，在符合条件的子串中找到最小的子串

? ? ? ? 其中就涉及到一个问题，我们如何知道子串是否含有t 字符串中所有字符，我们可以通过哈希表来解决这个问题，我们可以利用哈希表 hash1 来存储 t 字符串中所有字符对应的数目，以字符为key，字符的个数为 value，再利用哈希表 hash2 来存储子串中所有字符对应的数目，进行比对，我们便知道子串中是否含有? t 字符串中所有字符

? ? ? ? 关于子串的题，一般我们可以使用滑动窗口的方式来解决

? ? ? ? 以示例1为例：输入：s = "ADOBECODEBANC", t = "ABC"

? ? ? ? 首先，我们需要在 hash1 中记录 t 字符串中所有字符对应的数目，即：A - 1,B - 1,C - 1,

? ? ? ? 由于需要遍历字符串 s 中的所有子串，所以 L 和 R 指针指向下标 0，我们记录?R 指针指向的字符，在 hash2 中记录 A-1，由于在 hash2 中 A 字符的个数小于等于在 hash1 中 A 字符的个数所以当前记录的 A 字符是有效字符（因为 hash1 中的是需要的字符，hash2 中的是已有字符，如果已有字符小于等于需要的字符，那么该字符就是有效字符，反之，该字符就是多余的，就不是有效字符），我们用变量 count 来记录有效字符的个数，此时 count = 1

A????????D????????O????????B????????E????????C????????O????????D????????E????????B????????A????????N????????C

L

R

? ? ? ? 此时有效字符的个数还不满足要求（有效字符的个数要等于字符串 t 中的字符个数），所以 R 指针向右移，扩大讨论的子串,记录?R 指针指向的字符，在 hash2 中记录 D-1,?hash1 中没有记录字符 D 默认为 0 ，所以此时在 hash2 中 D?字符的个数大于在 hash1 中 D 字符的个数所以当前记录的 D?字符是无效字符，count 不修改

A????????D????????O????????B????????E????????C????????O????????D????????E????????B????????A????????N????????C

L

? ? ? ? ? R? ?

? ? ? ? 只要 count 的数目不为字符串 t 中的字符个数，就代表子串没有包含字符串 t 中的所有字符，我们就需要一直移动 R 指针，扩大讨论的子串

? ? ? ? 直到 R 指针指向当前位置，此时 count 的数目为 3 等于字符串 t 的字符个数，代表子串包含了字符串 t 中的所有字符，我们记录当前子串的长度，以及 L 指针的值（可以通过这两个信息从字符串 s 中截取出子串）

? ? ? ? 此时以 L 指针为首的子串讨论完毕，需要移动 L 指针，讨论下一批子串

A????????D????????O????????B????????E????????C????????O????????D????????E????????B????????A????????N????????C

L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R? ??

? ? ? ? L 指针向右移动前，我们需要判断 L 指针指向的字符是否是有效字符，L 指针指向的字符是 A , A 字符在 hash2 中的个数为 1，在 hash1 中的个数为 1，所以该字符 A 是有效字符，在 L 指针移动前需要将 hash2 中的个数减 1 ，即在 hash2 中 A-0，count 减 1 为 2

? ? ? ? 此时 子串不符合要求，R 指针向右移动，扩大讨论的子串

? ? ? ? 此时涉及到一个问题，R 指针需要回到 L 指针所在的位置从头开始讨论子串吗？答案是：不需要，因为 R 指针到达当前位置才满足条件包含了字符串 t 中的所有字符，当 L 指针向右移动只会出现两种情况：

????????一种是 L 指针原来指向的字符不是有效字符，此时 L 和 R 之间的子串依然满足要求，但要 R 指针在当前位置才满足要求，即使 R 指针回到 L 指针的位置，最后也会移动到当前位置

? ? ? ? 一种是 L 指针原来指向的字符是有效字符，此时 L 和 R 之间的子串不满足要求，需要 R 指针向右移动，扩大讨论的子串，所以即使 R 指针回到 L 指针的位置，也需要回到现在的位置再向右移动

A????????D????????O????????B????????E????????C????????O????????D????????E????????B?? ? ? ?A????????N????????C

? ? ? ? ? ?L? ??????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R? ?

? ? ? ? 当 R 指针到当前位置时 count =3，满足要求，此时以 L 指针为首的子串讨论完毕，需要移动 L 指针，讨论下一批子串

A????????D????????O????????B????????E????????C????????O????????D????????E????????B?? ? ? ?A????????N????????C

? ? ? ? ? ?L? ??????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R??

? ? ? ? L 指针原来指向的字符是 D ，不是有效字符，所以 L 指针向右移动以后依然符合要求，所以以 L 指针为首的子串直接讨论完毕，继续移动 L 指针

A????????D????????O????????B????????E????????C????????O????????D????????E????????B?? ? ? ?A????????N????????C

? ? ? ? ? ? ? ? ? ? ? L? ? ?? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R??

? ? ? ? 直到移动到当前位置，少了一个有效字符，才移动 R 指针扩大讨论的子串

A????????D????????O????????B????????E????????C????????O????????D????????E????????B?? ? ? ?A????????N????????C

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L?? ? ?? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R??

? ? ? ? 剩下的就是上述的流程的循环