BM90 题解 | #最小覆盖子串#

官方题解：双指针 + 哈希数组

说在前面：

因为26个字母算上大小写一共就52位，并且每一位的下标都可以由字符对应的ASCII码来获得

（比如'a' = 97，hash['a'] -> hash[97]）

所以这题不需要使用HashMap，使用数组作为哈希结构就行了。

思路：

这个解法的思路就是使用一个哈希数组来记录T中每个字符的出现次数

• 哈希数组在初始化的时候把T中每个字符对应的位置的值-1。
• 如果是AbA，那么'A'（ASCII为60）对应在哈希数组中就表现为：hash[60] = -2， 'b'：hash[98] = -1
• 使用双指针进行遍历：
• fast指针向右移动一位，就把当前这一位在哈希数组中对应的次数+1
• 然后判断当前哈希数组中是否有负数的值
• 如果哈希数组中存在负值，说明T中还有元素没有被包含进来的。
• 如果哈希数组中所有值都为正，说明当前窗口内的元素已经可以包含T中的所有字符了。
• 记录当前最优解
• 移动slow指针。为什么是移动slow指针？因为是从左往右遍历的，所以缩小窗口不能把fast指针往左缩小。所以要把左指针往右移动，看看是不是移动之后还能满足T中的所有字符，求一个最小长度

注释很详细

import java.util.*;


public class Solution {
    // 本题使用的是一个哈希数组
    // 检查是否有小于0的元素
    boolean check(int[] hash) {
        for (int i = 0; i < hash.length; ++i) {
            if (hash[i] < 0)
                return false;
        }
        return true;
    }
    public String minWindow (String S, String T) {
	  // 记录结果子串的字符个数
        int count = S.length() + 1;
        
        // a-z为97-122。A-Z为65-90。所以这里数组长度才设了一个128，其实真正使用的只有26*2个
        // 这个哈希数组中存放了a-z A-Z出现的次数
        // 初始化的时候T中的元素全都-=。其他元素都不管
        // 后续在遍历的时候，每遍历到一个元素，就在这个元素对应的位置上+1
        // 这样，T之外的元素不受影响，T里面的元素满足了个数就会 >=0
        // 我们只要查看哈希数组中是否有0以下的数，如果有，就说明窗口没有完全包含T，如果没有，就说明已经完全包含T了
        int[] hash = new int[128];
        for (int i = 0; i < T.length(); ++i) {
            hash[T.charAt(i)] -= 1;
        }
        // 双指针
        int slow = 0, fast = 0;
        // 记录左右区间
        int left = -1, right = -1;
        for (; fast < S.length(); ++fast) {
            char c = S.charAt(fast);
            // 遍历到字符就把哈希数组中对应的元素+1
            hash[c]++;
            // 如果滑动窗口中没有小于0的元素说明都被覆盖了。
            // 此时窗口中的元素已经能包含T中的所有元素了
            // 这个时候fast还在当前轮次，slow开始向右移动，以寻求更短的，符合条件的子串
            while (check(hash)) {
                // 取最短的
                if (count > fast - slow + 1) {
                    count = fast - slow + 1;        // 记录当前最优解
                    left = slow;                    // 记录当前窗口
                    right = fast;
                }
                c = S.charAt(slow);
                // 缩小窗口
                hash[c]--;  // 因为是向右收缩窗口，所以把最左边的元素从窗口中剔除
                slow++;
            }
        }
        // 找不到的情况
        // 上面left的初始化就是-1，并且此时没有任何返回，说明left还没有动过
        // 因为一旦找到了，left就移到slow的位置，所以当left == -1时一定是没找到
        if (left == -1) { 
            return "";
        }
        return S.substring(left, right + 1); // 左闭右开所以要多+1
    }
}