LeetCode HOT 100 —— 76 .最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串"" 。

思路

滑动窗口：题目要求返回字符串s中包含字符串t的全部字符的最小窗口，即包含t的全部字符的窗口为可行窗口，所以可以用滑动窗口的思想解决这个问题

滑动窗口中的问题都会有两个指针，一个用于「延伸」现有窗口的r指针（相当于扩大右边界），和一个用于「收缩」窗口的 l 指针（相当于缩小左边界），在任意时刻，只有一个指针运动，而另一个保持静止

本题，在s上滑动窗口，通过指针r不断扩大窗口，当窗口包含t所需的全部字符后，如果能进行收缩，就进行收缩直到得到最小窗口，比如s="ABAACBAB",t="ABC"，那么滑动窗口从s最开始滑动，只要窗口内没有包含'A','B','C',就r右移，直到窗口内包含'A','B','C'的时候（正好达到t中字符的个数），停止r指针；接着开始l右移缩小窗口，只要窗口内一直保持'A','B','C'就一直右移，直到不满足这个要求，停止l指针，开始r右移继续判断直到窗口内又重新包含'A','B','C'为止，循环下去…

对于判断当前窗口是否包含t所需的全部字符，可以用一个哈希表来表示t中所有的字符以及它们的个数，然后用另一个哈希表动态维护窗口中的所有字符以及它们的个数，并额外设置一个计数cnt，不断更新右指针right，判断滑动窗口当前是否到达字符串t所要求的字符数量，没有达到则cnt++，达到之后，判断左指针left，可以收缩则cnt--

class Solution {
    public String minWindow(String s, String t) {
        //1.维护两个map记录窗口中的符合条件的字符以及need的字符
        HashMap<Character,Integer> window = new HashMap<Character,Integer>();
        HashMap<Character,Integer> need = new HashMap<Character,Integer>();

        for(char c : t.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        String ans = "";
        //len用来记录最终窗口的长度，并且以len作比较，淘汰选出最小的子串的len
        //cnt维护的是s字符串[left, right]区间中满足t字符串的元素的个数，记录相对应字符的总数
        int len = Integer.MAX_VALUE, cnt = 0;
        for(int left = 0, right = 0; right < s.length(); right++){//双指针,也可以用while，但是要注意right++需要放在while循环的最后面，就像for循环，全部执行完才right++，因为后续会用到right进行比较，所以一定要最后right++
            //更新窗口
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if(need.containsKey(c) && window.get(c) <= need.get(c))//说明当前新加入的字符c是必需的，且还未到达字符串t所要求的数量 
                cnt++;//新加入的字符c必需，则cnt++
            while(left < right && (!need.containsKey(s.charAt(left)) || window.get(s.charAt(left)) > need.get(s.charAt(left)))){//如果滑动窗口中s[left]的数量多于字符串t中s[left]的数量
                //收缩左边界
                window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                left++;
            }
            //当cnt == t.length()时，说明此时滑动窗口包含字符串 t 的全部字符，重复，取最小值
            if(cnt == t.length() && right - left + 1 < len){
                len = right - left + 1;
                ans = s.substring(left, right + 1);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33