76. 最小覆盖子串

 最小覆盖子串

思路：

1.双指针 一左一右维护一个滑动窗口

2.开两个哈希表。一个存t中的字符出现的次数，一个存当前窗口中的各字符的次数

双指针移动规则？

        右指针只要没有移出s的右边界就一直尝试往右移动，最终是要把s中的每一个字符都跑过一遍，因为要找最小的覆盖子串。

        右指针放大循环，里面加一个判断，当t中每个字符都被覆盖的时候，就可以把左指针往右移动，每移出一个，判断这个是不是t中的，如果是的话，对滑动窗口的性质进行更新。直至不满足覆盖串的性质，继续移动右指针。

代码：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> t_count;//存t中每个字符的个数
        unordered_map<char,int> s_count;//存当前窗口中各个字符的个数
       
        for(auto u:t) t_count[u]++;//初始化
        int left=0,right=0;//左右指针
        int ans_len=0x3f3f3f3f;//最小长度
        int ans_left=0;//最小窗口的左边界位置
        int t_different_count=t_count.size();//t中有多少个键
        int satis_count=0;//当前窗口中满足在t中且对应数量也满足的字符个数，等于t_different_count时则说明当前窗口是满足覆盖窗口的性质的。

        while(right<s.length())
        {
            char tchar=s[right];//当前字符
            s_count[tchar]++;//更新map
            if(t_count.find(tchar)!=t_count.end()&&s_count[tchar]==t_count[tchar])
            {//如果当前字符在t中且个数满足要求
                satis_count++;
            }
            while(left<=right&&satis_count==t_different_count)//t中每个字符都满足要求，开始更新左边界
            {
                if(right-left+1<ans_len)//满足条件的每一个窗口都要更新一下答案
                {
                    ans_left=left;
                    ans_len=right-left+1;
                }
                if(t_count.find(s[left])!=t_count.end()&&s_count[s[left]]==t_count[s[left]])
                {//如果左边界移出去的是t中的，作出更新。
                    satis_count--;
                }
                //移出去的字符进行统计
                s_count[s[left]]--;
                left++;
            }
            right++;
        }
        return ans_len==0x3f3f3f3f?"":s.substr(ans_left,ans_len);
    }
};