在做题中学习（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);
    }
};