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

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

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

看到这道题很多同学的第一反应就是暴力求解，暴力求解当然是可以做出来的，但是在校招笔试题或者面试题中，这样的方法都是需要被优化的，否则笔试只会有少部分案例通过，然后显示时间复杂度过大，所以我们刷题不能仅仅是做出来，尽量要求出最优解。

这道题我们用滑动窗口来解题更加方便。滑动窗口的思想就是利用双指针。首先我们将左右指针都指向s字符串的开头，然后右指针向右移，一直到滑动窗口满足覆盖子串停止，然后再移动左指针来减少当前滑动窗口左边的冗余字符，一旦通过左指针的移动导致滑动窗口中不满足覆盖子串，那么右指针继续移动，直到再次满足覆盖子串，或者达到s的长度停止。下面直接上代码，虽然是难题，但是该代码并不难。

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);
    }

这个解法的点睛之处就在于利用频数map和match来判断是否是覆盖字串。

欢迎大家有更好的解法和思路一起讨论。