滑动窗口-76.最小覆盖子串-力扣(LeetCode)
一、题目解析
1.不符合要求则返回空串("")
2.子串中重复字符的数量要不少于t中该字符的数量
二、算法原理
解法1：暴力枚举+哈希表
这里的暴力枚举也可以优化，即在包含t中元素处枚举，如在A、B和C处开始枚举，减少不必要的枚举
解法2：滑动窗口+哈希表+check函数判断
why？为什么能使用滑动窗口
能观察出left和right同向移动，left和right的间距就像一个窗口一样，框出符合要求的字符串
how？如何实现滑动窗口？
1.定义left和right
2.check函数：判断s的哈希表包含的元素是否大于等于t的哈希表
3.进窗口->hash2[in]++
4.判断->check(hash1,hash2)
5.更新结果->更新结果需要记录起始位置和最短长度
出窗口->hash2[out]--
解法3：滑动窗口+哈希表+count变量优化判断条件
对于check()函数，需要遍历两个哈希表所以元素，所以可以通过count来记录有效字符的种类，通过维护count来实现简便判断
1.进窗口->进窗口之后，当hash1[in] == hash2[in]时，count++
2.出窗口->出窗口之前，当hash1[out] == hash2[out]时，count--
3.判断条件->当count == kinds(t中有效元素的个数)
在理解why后，可以先解法2，然后再去尝试解法3
三、代码示例
解法2：
bool check(int hash2[], int hash1[]){for (int i = 'A'; i <= 'Z'; i++) {if (hash2[i] < hash1[i]) return false;}for (int i = 'a'; i <= 'z'; i++) {if (hash2[i] < hash1[i]) return false;}return true;}public:string minWindow(string s, string t) {int hash2[128]={0}; // s 子串字母的出现次数int hash1[128]={0}; // t 中字母的出现次数for (char c : t) {hash1[c]++;}int m = s.size();int minlen = INT_MAX,begin = -1;for (int left = 0,right = 0; right < m; right++) {hash2[s[right]]++; // 右端点字母移入子串while (check(hash2, hash1)) { // 涵盖if (right - left +1< minlen) { // 找到更短的子串minlen = right-left+1;begin = left;}hash2[s[left]]--; // 左端点字母移出子串left++;}}return begin < 0 ? "" : s.substr(begin, minlen);}
}; 
解法3：
string minWindow(string s, string t){int hash1[128] = {0};//统计字符串t中每一个字符的频次int kinds = 0;//统计有效字符由多少种for(auto ch : t)if(hash1[ch]++ == 0) kinds++;int hash2[128] = {0};//统计窗口内每个字符的频次int minlen = INT_MAX,begin = -1;for(int left = 0,right = 0,count = 0;right<s.size();right++){char in = s[right];if(++hash2[in] == hash1[in]) count++;//进窗口+维护countwhile(count == kinds){if(right-left+1<minlen){minlen = right-left+1;begin = left;}char out = s[left++];if(hash2[out]-- == hash1[out]) count--;}}if(begin == -1) return "";else return s.substr(begin,minlen);}