本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析，有需要借鉴即可。
1.题目
题目链接：LINK
这个题目是困难难度，感觉是一个中等题目的感觉。
首先我肯定想到的是暴力求解的方法，大概就是下面这种思路：
在比较找出的子串是否满足条件时候，可以用有效字符的方法，比如下面代码的count计数。
class Solution { public: //暴力求解： string minWindow(string s, string t) { //定义一个哈希表，用来收集t的有关信息 string ret = ""; int hash_t[128] = {0}; for(int i = 0; i < t.size(); i++) { hash_t[t[i]]++; } int minlength = 0; for(int left = 0; left < s.size(); left++) { int hash_s[128] = {0}; int count = 0; for(int right = left; right < s.size(); right++) { //进哈希表 hash_s[s[right]]++; if(hash_s[s[right]] <= hash_t[s[right]])count++;//有效字符++ //判断 if(count == t.size() && (minlength==0 || minlength >= right - left + 1)) { minlength = right - left + 1;//有结果就把这次的长度更新过来，下一次比较的时候用 ret = s.substr(left, minlength); break; } } } return ret; } };
count有效计数原理：
当我们进哈希数组时候，如果这个字符映射的数组值小于等于hash_t的对应数组，则就是需要的，那么count就++，反之则不是
同理，当我们出字符时候，也是这个道理。
2.滑动窗口解法
但是我们可以发现，left 和 right是可以不用回退一直向前的，这就满足双指针，滑动窗口算法的使用条件
所以，代码可以优化成下面代码：
class Solution { public: string minWindow(string s, string t) { //统计t的有关信息 int hash_t[128] = { 0 }; int kinds = 0; for(auto ch : t) { if(hash_t[ch]++ == 0)kinds++; } int start = -1; int length = INT_MAX; //统计s的有关信息 int hash_s[128] = { 0 }; for(int left = 0, right = 0, count = 0; right < s.size(); right++) { //进窗口 char in = s[right]; hash_s[in]++; if(hash_s[in] == hash_t[in])count++; //判断 while(count == kinds) { //更新结果 if(right - left + 1 < length) { length = right - left + 1; start = left; } //出窗口 char out = s[left]; if(hash_s[out] == hash_t[out]) count--; hash_s[out]--; left++; } } if(start == -1)return ""; else return s.substr(start, length); } };
注：这个地方的count计数与暴力求解的计数区别是这里用的是字母种类个数。
3.总结
如果有前面“滑动窗口”的题目铺垫其实这道题并不难，需要用到count计数的优化以及滑动窗口的思想。
EOF
