滑動窗口系列-尋找最小覆蓋字串

總結：

need容器中存放的是需要覆蓋的字串，包括字符和對應的字符數量
1.用最小覆蓋字符串在原字符串中的首字母比特置和最小覆蓋字符串的長度錶示最小覆蓋字符串；
2.左、右指針的含義是指向原字符串的左右比特置上的，是原字符串的一段數據；
3.window窗口中保存的是左、右指針所指數據段上符合要求的數據（在need容器中）；
4.右指針往右進行數據的擴大，尋找可行解；左指針往右進行數據的縮小，尋找最優解；
5.指針變化的時候怎麼更新window窗口中的數據，要先根據need容器判斷當前指針指向的數據是否需要加入window(放入right所指的元素)，或者當前window中
是否有元素需要移除(left所指的元素在當前window中)。
6.窗口收縮的判斷，通過設置valid，看是否已經包含所有要尋找的字符串，然後進行窗口的收縮。

class Solution {
public:
//怎麼錶示最小覆蓋字串 
    string minWindow(string s, string t) {
        unordered_map<char, int > need;
        unordered_map<char, int > window;
        for(auto value:t) need[value]++;//如果該key不存在的話，會自動創建該key，並把map[key]賦值為0

        int left=0,right=0;
        int valid=0;//錶示已經滿足要求的字符個數
        //通過字符串的首字符的比特置和字符串的長度來確定最小覆蓋字串
        int start=0;
        int Len=INT_MAX;
        while(right<s.size()){
            //尋找可行解
            //取出字符放入到窗口，更新窗口數據
            char c=s[right];
            right++;//窗口滑動
            if(need.count(c)){//如果是需要的字符就把它放入到窗口中，並判斷該字符是否數量已經滿足要求
                window[c]++;
                if(window[c]==need[c]){//window中維護的是左、右指針間的和need容器中元素相同的量
                    valid++; //valid控制每個字符都達到要求了
                }
            
            }
            //尋找最優解，開始收縮窗口
            while(valid==need.size()){
                if(right-left<Len)
                {
                    start=left;
                    Len=right-left;
                }
                //left右移
                char c=s[left];//判斷left指的元素是否在窗口中
                left++;
                if(need.count(c)){

                    if(need[c]==window[c]){//注意這裏和加入元素的時候的順序是相反的
                        valid--;
                    }
                    window[c]--;

                }


            }



        }
        return Len==INT_MAX?"":s.substr(start,Len);


    }
};