跳转原题

题目描述：

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

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：求满足符合数量要求的最短字串，可以用滑动窗口算法解决

在滑动窗口模板中，我们要关注何时缩小窗口，实际上再找到符合条目要求的字串后就需要收缩窗口，这其实是一个寻找最优解的过程。换句话说，通过聪明的穷举来获取那个最短切符合题目要求的字串；

Java版本如下：

class Solution {
    public String minWindow(String s, String t) {
        int left=0;
        int right=0;
        int len=Integer.MAX_VALUE,start=0;
        //左右指针
        //窗口
        HashMap<Character,Integer> window=new HashMap();
        HashMap<Character,Integer> need=new HashMap();
        for(int i=0;i<t.length();i++){
            char c=t.charAt(i);//获取i索引位置字符
            //统计
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int valid=0;
        while(right<s.length()){
            char c=s.charAt(right);
            
            right++;
            //更新窗口直到满足个数
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                //接下来可以1.通过比较valid（某个字母个数相同会自增），知道valid与need长度一样。但不能通过累加个数，因为这是映射，不知道谁多谁少
                if(window.get(c).equals(need.get(c)))
                valid++;
            }
            //收缩时机是窗口中满足最小字串个数
            while(valid==need.size()){
                //更新窗口长度
                if(right-left<len){
                    //通过start来记住此时此刻的窗口，但不一定最小
                    start=left;
                    len=right-left;
                }
                char d=s.charAt(left);
                left++;
                //youyi 记录被移除的元素
                //可能会不符合条件，也可能符合
                // if(need.containsKey(d)&&window.get(d).equals(need.get(d))){
                // valid--;
                // window.put(d,window.get(d)-1);}
                 if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        //求最小长度时用max记录len 
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }
}

在看了大致题解后自己去写时，我犯了很多错误。包括但不限于

1.containsKey关键字1拼错

2.不知到需要那些变量来记录

3.收缩窗口时if内部的处理：vaild不一定--；但window窗口一定缩小