滑动窗口最终弹

 力扣30.串联所有单词的子串（巨困难）

这个最难的是什么

1.代码的编写

2.容器的使用 

class Solution {
    List<Integer>ret=new LinkedList<>();
    //保存字典中所有单词的频次
    public List<Integer> findSubstring(String s, String[] words) {
     Map<String,Integer>hash=new HashMap<String,Integer>();
     for(String str: words){
       hash.put(str,hash.getOrDefault(str,0)+1);
         }
     int len=words[0].length();
     //表示word一个字符串的长度
     int m=words.length;
     //count应该是代表有效的字符串个数
     //用于存储字符串
   
     for(int i=0;i<len;i++){
         //进窗口，count每次循环之后都恢复为0
           Map<String,Integer>hash2=new HashMap<String,Integer>();
         for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
             String in=s.substring(right,right+len);
             hash2.put(in,hash2.getOrDefault(in,0)+1);
             //因为是一个字符串，我在hash里已经把全部的字符串存进去了，我最后要求的
             //所有字符串的组合起来，然后看s里面有没有
             //换句话说，必须是组合，那么假如s里面存在重复的有效子串但是words里面没有这些子串
             //那么就说明一件事情，这个不是有效长度，不给予count++
             //注意这里的小于等于不是说让你添加，他此时假如说正好等于那么我有效字符串的数量还是要+1的
             if(hash2.get(in)<=hash.getOrDefault(in,0)){
                 count++;
             }
//看现在包含的长度，是不是有效字符串的长度，假如说比他要大了
             if(right-left+1>len*m ){
                 //出窗口
                 String out=s.substring(left,left+len);
                //还是要判断出去的是不是有效的子串
                 if(hash2.get(out)<=hash.getOrDefault(out,0))
            //注意这里的小于等于不是说让你添加，他此时假如说正好等于那么我有效字符串的数量还是要-1的
                     count--;
               hash2.put(out,hash2.get(out)-1);
                 left+=len;
             }
             if(count==m) ret.add(left);
         }
     }
        return ret;
   }
   }

力扣76.最小覆盖子串(较苦难）

这种题都很锻炼代码的编写

left=0,right=0

1.进窗口 hash[in]++

判断条件:check(hash1,hash2)

更新结果-起始位置，最短长度

2.出窗口 hash2[out]--

优化：判断条件

使用count标记有效字符的种类

能明白啥意思，但是不好写，建议明天回顾一手

class Solution {
    public String minWindow(String ss, String tt) {
    int minlen=Integer.MAX_VALUE;
    //假如说大写小写都包括，那么就直接128
    //统计字符串t中字符的频次
    int []hash1=new int[128];
    //统计窗口中字符的频次
    int []hash2=new int[128];
    //用来表示字符串字符有多少种
    int kinds=0;
    char[]t1=tt.toCharArray();
    char[]s=ss.toCharArray();
    int count=0;
    int begin=-1;
    //统计字符串t中字符的频次,kinds用来表示字符有多少种
    for(char a:t1){
        //如果之前没有存储这个字符串，那么kinds就++
        if(hash1[a]==0)kinds++;
        hash1[a]++;
    }
        for(int left=0,right=0;right<s.length;right++){
            char in=s[right];
            //java好像是可以自动转化，可以把字符自动转化成对应的ac数值
            hash2[in]++;//进窗口
            //假如两个哈希表里面的值相同count才会++,因为记录的是有效字符
            if(hash2[in]==hash1[in])count++;
            while(kinds==count){

                if(right-left+1<minlen){
                    //保留当前值
                    begin=left;
                    //更新最短的长度
                    minlen=right-left+1;
                }
                //出窗口
                char out=s[left];
                //假如出的是有效字符，才会count--
                if(hash1[out]==hash2[out])count--;
                 left++;
                 //出窗口
                 hash2[out]--;
            }
            //假如说count和t存储的字符种类一样，那么
            if(count==tt.length()){
               begin=left;
               left=right+1;
            }
        }
     if(begin==-1) return new String();
     else return ss.substring(begin,begin+minlen);
    }
}