image.png

解法

下面解法不是最优解，后续再优化

Map<Character, Integer> targetMap = new HashMap<>();
    Map<Character, Integer> countMap = new HashMap<>();

    public String minWindow(String s, String t) {
        // 目标map中的字符数
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }
        int ansL = -1;
        int ansR = -1;
        int minLen = Integer.MAX_VALUE;
        int l = 0;
        int r = -1;
        while (r < s.length()) {
            r++;
            // 存在s中的字符则对应字符加1
            if (r < s.length() && targetMap.containsKey(s.charAt(r))) {
                countMap.put(s.charAt(r), countMap.getOrDefault(s.charAt(r), 0) + 1);
            }
            // 满足条件，则收缩左边，找最小长度，直到不满足条件
            // 此时l向后多移动了一位，接着移动r,继续寻找，直到r到字符串末尾
            while (checkContain() && l <= r) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    ansL = l;
                    ansR = r;
                }
                if (targetMap.containsKey(s.charAt(l))) {
                    countMap.put(s.charAt(l), countMap.getOrDefault(s.charAt(l), 0) - 1);
                }
                l++;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR + 1);
    }

    /**
     * 校验countMap是否完全包含了targetMap
     */
    private boolean checkContain() {
        for (Map.Entry<Character, Integer> entry : targetMap.entrySet()) {
            char key = entry.getKey();
            if (countMap.getOrDefault(key, 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }

优化后的方法，滑动窗口进行滑动，会移动左指针，过滤掉多余的左指针。

class Solution {
    public String minWindow(String s, String t) {
        // 数组当hash用，操作更快，更节省空间
        int[] target = new int[128];
        int[] count = new int[128];

        for (char ch : t.toCharArray()) {
            target[ch]++;
        }
        String str = "";
        int l = 0;
        // 遍历顺序当右边界
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
            // 不断移动左边界，只要count中对应的字符大于target中,就减一
            // 滑动窗口的精髓
            while (l <= i && count[s.charAt(l)] > target[s.charAt(l)]) {
                count[s.charAt(l)]--;
                l++;
            }
            // 校验count是否包含了target
            if (checkContain(target, count)) {
                if (str.length() == 0) {
                    str = s.substring(l, i + 1);
                } else {
                    if (i - l + 1 < str.length()) {
                        str = s.substring(l, i + 1);
                    }
                }
            }
        }
        return str;
    }

    private boolean checkContain(int[] target, int[] count) {
        for (int i = 0; i < target.length; i++) {
            if (target[i] > count[i]) {
                return false;
            }
        }
        return true;
    }
}