题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

样例

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

算法

y总提供的思路 双指针 + 哈希表快速判断是否覆盖

在Java中频繁对哈希进行更改的效率比数组低，所以选用数组来代替哈希，对字符个数进行计数。
简直不能更棒！

参考文献

https://www.acwing.com/solution/LeetCode/content/160/
配合视频服用效果更好：https://www.bilibili.com/video/av64330434

Java 代码

class Solution {
    public String minWindow(String s, String t) {
        String ret = "";
        if (s.length() < t.length()) return ret;

        // 利用数组来保存字符串 t 中每个元素出现的个数
        int[] hash = new int[128];
        for (int i = 0; i < t.length(); i ++) hash[t.charAt(i) - 'A'] ++;

        int cnt = 0;
        for (int a : hash) {
            if (a > 0) cnt ++;
        }

        char[] chars = s.toCharArray();
        for (int i = 0, j = 0, c = 0; i < chars.length; i ++) {
            // 刚好找到一个字符 计数器 ++
            if (hash[chars[i] - 'A'] == 1) c ++; 
            // 不管是不是 t 中的元素，都 --
            hash[chars[i] - 'A'] --;
            // 在找到完了元素之后才对指针 j 进行后移
            while (c == cnt && hash[chars[j] - 'A'] < 0) hash[chars[j ++] - 'A'] ++;
            // 更新结果
            if (c == cnt) {
                if (ret == "" || ret.length() > i - j + 1) {
                    ret = s.substring(j, i + 1);
                }
            }
        }
        return ret;
    }
}