一、題目解析
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);}
?
