76. 最小覆盖子串-蒲公英云

76. 最小覆盖子串

先上滑动窗口模板

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
示例 2：

输入：s = “a”, t = “a”
输出：”a”

class Solution {
    public String minWindow(String s, String t) {
        /**
        滑动窗口:
            步骤一: 窗口不包含t r右移
            步骤二: 窗口包含t l右移 不断缩小边界 然后又重复步骤一
         */
         int need[]=new int[130];//某一个字符的ASCII码出现的次数  63-121 开一个130的
         int left=0,right=0,count=t.length(),start=0,size=Integer.MAX_VALUE;
         //初始化
         for(int i=0;i<t.length();i++){
             need[t.charAt(i)]++;
         }
         while(right<s.length()){
             char c=s.charAt(right);
             if(need[c]>0){//t里面有这个字符
                 count--;//还需要的count数量-1
             }
             need[c]--;//找到他的一个字符
             if(count==0){//找到全部字符, left++
                while(left<right&&need[s.charAt(left)]<0){//need[left]<0才可以右移  就是多出现的 比如要找ABC   AABBC 那么A可以右移一次
                    need[s.charAt(left)]++;
                    left++;
                }
                //退出说明不能再走了
                if(right-left+1<size){
                    size=right-left+1;
                    start=left;
                }    
                //再重新更新下left ,重新维护窗口  移出左边的那个
                need[s.charAt(left)]++;
                left++;
                count++;
             }
              right++;//不断右移指针
         }
         return size==Integer.MAX_VALUE?"":s.substring(start,start+size);
    }
}