题目描述
- 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 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;}
};
