每日一题-滑动窗口

目录

最小覆盖子串

最小覆盖子串

• 时间：0810
• 题目

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

• 思路
  • 剪枝：当s的长度小于t的时候，就凑不齐t的所有字符
  • 找到s中包含t中全部字母的最小子串，这个就用到了将字母字典作为下标的思路：
    • 初始化一个数组，数组下标就是字母，字母在t中出现过++
    • 再遍历s，遇到一个字母，就对应整型数组的值就，当遇到减完之后还大等于0的，就证明在t中出现过，否则减完就是负数拉
    • 当记录的t中的字符都出现过的时候，就记录当前子串的长度
      • ️️ 还有一点就是，恢复滑动窗口左窗口左侧的所有值，这样当再出现的时候，不会误判
• 代码

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null || s.length() < t.length())
            return "";
        char[] s_ch = s.toCharArray();
        char[] t_ch = t.toCharArray();
        int[] map = new int[256];
        //t字母对应的下标
        for(int i = 0; i < t.length(); i ++){
            map[t_ch[i]] ++;
        }
        int toMatch = t.length();
        int minValue = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int res = 0;
        for(int i = 0; i < s.length(); i ++){
            map[s_ch[i]] --;
            if(map[s_ch[i]] >= 0)
                toMatch --;
            if(toMatch == 0){
                // 当前已经找到了t中的所有字符
                // 这里为什么这么写，是因为如果前面出现了重复的t的字符，但是又不属于窗口内的话，不加回来，就会导致窗口内的字符也会被丢弃，因为小雨0了
                while(map[s_ch[left]] < 0){
                    map[s_ch[left ++]] ++;
                }
                if(minValue > (right - left)){
                    minValue = right - left + 1;
                    res = left;
                }
                toMatch ++;
                map[s_ch[left ++]] ++;
            }
            right ++;
        }
        return minValue == Integer.MAX_VALUE ? "" : s.substring(res, res + minValue);
    }
}