Leetcode每日一题-76（5.23-java版本）

76.最小覆盖子串（困难）

public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        //对于t字符串进行词频统计，然后保存在map里面。
        HashMap<Character,Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
        //采用left和right双指针
        int left = 0, right = 0;
        //match用来统计当前的滑动窗口中包含满足t字符串的字符数。
        // （这句话要好好理解）比如当前的滑动窗口是abaac，t字符串是abcd，那么当前的match就是3。
        int match = 0;
        //这里的minLen的初值选择最大值，也就是s的长度+1即可，不用过多追究。
        int minLen = s.length() + 1;
        //下面的start和end是最终要输出的符合要求的字符串开始和终止的字符位置。
        int start = 0, end = 0;
        //这个循环可以看作是右边界的扩充。
        while (right < s.length()){
            char charRight = s.charAt(right);
            //如果扩充的右边界中有符合t字符串的字符，那么将map中的对应字符的频数减一。
            if(map.containsKey(charRight)){
                map.put(charRight,map.get(charRight)-1);
                //如果频数减一以后它的频数>=0，那么将match++，也就是说我们找到一个满足t字符串中的字符。
                if(map.get(charRight)>=0)match++;
            }
           right++;
            //该循环是右边界确定的情况下，也就是当match==t.length()说明了我们当前的滑动窗口满足t字符串。
            //但是我们的滑动窗口可能过长，例如假设我们滑动窗口是abaacd，t字符串是abcd，
            // 可以看到baacd就能覆盖abcd了，左边有冗余a，所以这个循环的目的就是去除左边的冗余。
            while (match == t.length()){
                //下面是对于最小覆盖字串开始和终止字符位置的记录。
                int size = right - left;
                if (size < minLen){
                    minLen = size;
                    start = left;
                    end = right;
                }
                //既然当前的滑动窗口中可能存在冗余，那么我们判断左边的字符。
                // 如果左边的字符不在t中则直接过，如果在t中，那么将其的频数加1，然后再次判断频数，如果超过1，那么说明当前左移以后的滑动窗口不能包含t字符串，所以match--，然后跳出循环继续右扩。
                char charLeft = s.charAt(left);
                if(map.containsKey(charLeft)){
                    map.put(charLeft,map.get(charLeft)+1);
                    if(map.get(charLeft)>0) match--;
                }
                left++;
            }
        }
        return s.substring(start, end);
    }