代码改写自： labuladong 的算法小抄
题目来源自： leetcode 76. 最小覆盖子串

题目描述

具体代码

class Solution {
    public String minWindow(String s, String t) {
        // 滑动窗口（记录的是窗口内所有的元素以及其对应的个数）
        Map<Character, Integer> window = new HashMap<>();
        // 需求窗口（记录目标字符串对应的所有元素以及其对应的个数）
        Map<Character, Integer> need = new HashMap<>();
        // 初始化需求窗口
        for(char c : t.toCharArray()) {
            // need如果不存在该元素，则将其直接插入，且对应的个数为1；否则将其个数+1
            need.put(c, need.getOrDefault(c, 0).intValue() + 1);
        }
        // left、right分别为window的左右边界
        // 当window对应的某个元素个数达到了need的要求，valid+1
        // 如：need中要求元素'a'等于2, 则当window中的'a'也等于2时，valid+1
        // 当valid等于need的长度时，表明window已经达到了need中的所有元素的要求
        int right = 0, left = 0, valid = 0;
        // 用于记录最小子串的开始下标和长度
        int start = 0, length = Integer.MAX_VALUE;
        // 当window的右边界到达字符串边缘后退出循环
        while(right < s.length()) {
            // 取出当前元素，并将window右边界右移
            char c = s.charAt(right++);
            if(need.containsKey(c)) {
                // window对应的元素个数+1
                window.put(c, window.getOrDefault(c, 0).intValue() + 1);
                // 如果window中，该元素的个数符合了need的要求则valid+1
                if(window.get(c).intValue() == need.get(c).intValue()) {
                    ++valid;
                }
            }
            // 当valid等于need的长度时，表明window已经达到了need中的所有元素的要求,
            // 开始考虑window左侧是否需要缩减窗口
            while(valid == need.size()) {
                // 如果当前窗口的子串长度小于先前的子串，则用其替换
                if(right - left < length) {
                    start = left;
                    length = right - left;
                }
                // 取出当前的左侧元素，并将window左边界右移
                char d = s.charAt(left++);
                if(need.containsKey(d)) {
                    // 如果当前的左侧元素个数在window和need中对应的个数相同，
                    // 由于window需要缩减，所以window对应的元素的个数定然已经
                    // 不符合need所要求的个数了，因此valid也需要跟着-1
                    if(window.get(d).intValue() == need.get(d).intValue()) {
                        --valid;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);
    }
}