力扣-76-最小覆盖子串

public String minWindow(String s, String t) {
    HashMap<Character,Integer> need = new HashMap<>();//计数器，T中字符出现次数
    HashMap<Character,Integer> window = new HashMap<>();//计数器，窗口中相应字符出现次数

    int left = 0, right = 0;
    int valid = 0;//符合要求的字符个数
    int start = 0,end = 0,len = Integer.MAX_VALUE;//记录最小覆盖字串起始索引和长度，
    for(int i = 0;i<t.length();++i){//初始化need计数器
        char ch = t.charAt(i);
        //needs如果包含t.charAt(i)，则取出值+1;不包含取0+1
        need.put(ch,need.getOrDefault(ch,0)+1);
    }

    while(right < s.length()){
        char c = s.charAt(right); 
        //如果是t中字符，在window中添加，累计出现次数
        if(need.containsKey(c)){
            window.put(c,window.getOrDefault(c,0)+1);

            //Integer不能用==比较，要用compareTo
            if(window.get(c).compareTo(need.get(c)) == 0)    valid++;//符合要求字符加1
        }
        right ++;//右端加1

        //符合要求的字符数正好是t中所有字符，获得一个可行解
        while(valid == need.size()){
            //更新最小结果
            if(right - left < len){
                start = left;
                end = right;
                len = right - left;
            }
            //开始进行优化，缩小区间
            char d = s.charAt(left);

            if(need.containsKey(d)){//当前要删的字符在t内，更新window中对应字符出现次数
                window.put(d,window.getOrDefault(d,0)-1);
                //如果更新之后窗口字符出现次数 < t中字符出现次数，则符合要求字符数减1
                //就不会进入缩小区间这个循环
                if(window.get(d) < need.get(d))    valid--;
            }
            left ++;
        }
    }

    //返回覆盖的最小串
    return len==Integer.MAX_VALUE ? "" : s.substring(start,end);
}