在做题中学习（82）：最小覆盖子串

解法：同向双指针——>滑动窗口

思路：题目要求找到s里包含t所有字符的最小子串，这就需要记录在s中每次查找并扩大范围时所包含进去的字符种类是否和t的相同，并且：题目提示t中会有重复字符，因此不能简单认为只要记录s中t字符出现的次数，如： 会错误的判断出s子串aoab是符合要求的。

因此，我们比较的时候需要保证遍历出的 s子串 和 t 中字符种类 以及 字符数量 都保持一致，因此需要用到哈希表来记录，将s 和 t 中字符入哈希表，并保证找到s子串后的hash1 完全等于 t的hash2，便是一个合法的子串。

滑动窗口步骤：

1.left = 0,right = 0;

2.入窗口: hashs[s[r]]++;

3.判断: check(hashs[],hasht[])

4.更新结果: minlen = r - l + 1;   begin = l;

5.出窗口: hashs[s[l]]--; l++;

优化：

        check(hashs[],hasht[])是一件很费时的工作，要判断俩数组的元素种类对应的个数相不相同，需要循环遍历判断；因此优化判断工作：给hashs 和 hasht 都分别维护一个变量，记录有效字符的种类，如果俩变量相同，则说明此时窗口内的子串是一个合法的子串。

1.进窗口之后：if(hashs[s[r]] == hasht[s[r]]) count++;

2.判断: while(kind == count)

3出窗口之前: if(hashs[s[l]] == hasht[s[l]])  count--;

附上完整代码：

class Solution 
{
public:string minWindow(string s, string t) {int hashs[128] = {0};int hasht[128] = {0};int kind = 0;for(int i = 0;i<t.size();i++){if(hasht[t[i]]++ == 0)    kind++;}int minlen = INT_MAX,begin = -1;for(int l = 0,r = 0,count = 0;r<s.size();r++){hashs[s[r]]++;if(hashs[s[r]] == hasht[s[r]])count++;while(count == kind) {if(r - l + 1 < minlen){minlen = r - l + 1;begin = l;} if(hashs[s[l]] == hasht[s[l]])count--;hashs[s[l]]--;l++;}}if(begin == -1) return "";return s.substr(begin,minlen);}
};