力扣017_最小覆盖字串题解----C++

题目描述

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。、

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都大于或等于t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

假设这是我们对应的是s和t

创建unordered_map<char,int> hs,ht

我们定义两个指针，作为遍历s的窗口，再定义一个cnt作为窗口内的有效字符。

遍历s，用for循环，每循环一次r，把r指向的值存入到hs中，

 unordered_map<char,int> hs,ht;
        string ans;
        for(auto &c:t) ht[c]++; 
        int l=0,r=0,cnt=0; //l为窗口的左边界，r为窗口的右边界
        for(;r<s.size();r++){ //每次循环右边界右移一次
            hs[s[r]]++;

此时有两种情况，当hs[s[r]]<=ht[s[r]] ,cnt++。

如果hs[s[l]]>ht[s[l]],说明hs里面已经存在两个相同的有效值了，如下图

ht：ABA，cnt=2 因为我们要找的是最小覆盖字串，且包含了A有效字符，所有这个时候我们的左窗口右移，并且减去一个A

while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界，比如这个边界字符不在t里，
                hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同，那么就可以右移左边界
                l++;

一次次的循环如下

当我们的cnt 有效字符等于t.size()的时候，也就是这个窗口包含了t字符串的所有。

 if(cnt==t.size()){ //有效字符等于字符串t的长度，我们可以放入答案；
                if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1);或者对比前窗口的大小和当前的大小，然后决定是否更新ans。
            }

如下即为全部的代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> hs,ht;
        string ans;
        for(auto &c:t) ht[c]++; 
        int l=0,r=0,cnt=0; //l为窗口的左边界，r为窗口的右边界
        for(;r<s.size();r++){ //每次循环右边界右移一次
            hs[s[r]]++;
            if(hs[s[r]]<=ht[s[r]]) cnt++; //在找到第一个符合条件的窗口后，这个语句不会再运行了。
                                          //ps.该语句的作用是统计窗口内的有效字符
            //左边界右移                              
            while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界，比如这个边界字符不在t里，
                hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同，那么就可以右移左边界
                l++;
            }
            if(cnt==t.size()){ //有效字符等于字符串t的长度，我们可以放入答案；或者对比前窗口的大小和当前的大小，然后决定是否更新ans。
               if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1); 对比前窗口的大小和当前的大小，然后决定是否更新ans。
            }
        }
        return ans;
    }
};