LeetCode——最小覆盖子串

NO.76 最小覆盖子串困难

思路一：滑动窗口 双指针形成闭区间[left,right]作为窗口，开始时right移动不断增大窗口，当窗口内的子串满足要求时right停止；left开始移动不断缩小窗口，直至窗口内的子串不符合条件为止再变成right移动，每次left移动都要更新结果值。

开始移动right就是寻找符合要求的子串的过程，找到之后缩小窗口是对子串进行优化的过程。

最后就是如何判断窗口内的子串符合要求：先用一个map存储T的元素及其个数，再用一个map保存窗口中的元素及其个数。

public String minWindow(String s, String t) {
    if (s==null||s.equals("")||t==null||t.equals("")||t.length()>s.length())return "";
    //保存t中所有字符和个数
    Map<Character,Integer> allMap=new HashMap<>();
    //记录窗口中字符和个数
    Map<Character,Integer> window=new HashMap<>();
    //统计t中字符
    for (char c : t.toCharArray()) {
        allMap.put(c, allMap.getOrDefault(c,0)+1);
    }
    //left、right窗口边界，count窗口中符合要求的元素个数，minLen符合要求的最小子串长度
    int left=0,right=0,count=0,minLen=s.length();
    String res="";
    while (right < s.length()) {
        //当前元素计入窗口
        char c = s.charAt(right);
        window.put(c,window.getOrDefault(c,0)+1);
        //如果当前元素符合要求，则count++
        if (allMap.containsKey(c) && allMap.get(c) >= window.get(c)) {
            count++;
        }
        //当窗口子串符合条件即找到满足条件的子串，缩小窗口，进行子串优化
        while (count == t.length()) {
            char ch = s.charAt(left);
            //更新minLen，主要是<=  s:"aa" t:"aa"的情况也要更新
            if ((right - left + 1) <= minLen) {
                minLen=right-left+1;
                res=s.substring(left,right+1);
            }
            //缩小窗口
            if (allMap.containsKey(ch) && allMap.getOrDefault(ch, 0) >= window.get(ch)) {
                count--;
            }
            window.put(ch,window.get(ch)-1);
            left++;
        }
        right++;
    }
    return res;
}

时间复杂度：O(n) n是s的长度，最坏情况就是左右边界指针各遍历一次s，2n。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.76 最小覆盖子串 困难

NO.76 最小覆盖子串困难