76.最小覆蓋子串：
給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。
注意：
- 對于
t中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于t中該字符數(shù)量。 - 如果
s中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
示例 2：
輸入：s = "a", t = "a"
輸出："a"
示例 3:
輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個字符 'a' 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105-
s和t由英文字母組成
思路：
這又是一道可以利用滑動窗口進(jìn)行求解的題目，滑動窗口經(jīng)常用來解決這類字符匹配文藝，用于尋找最小或者最長子串。這道題在求解時，同樣需要用到哈希表，對出現(xiàn)的字符以及出現(xiàn)的個數(shù)進(jìn)行記錄。
數(shù)組型哈希表:
采用數(shù)組作為哈希表的形式。
首先對字符串T進(jìn)行遍歷，更新哈希表，記錄下需要的字符以及字符的數(shù)量。
接著對字符串S進(jìn)行滑動窗口遍歷，這里的一個難點就是如何判斷已經(jīng)找全了所有的字符。這里就運用到了變量lenT，即字符串T的長度。每當(dāng)找到符合條件的字符，都時lenT減一，那么當(dāng)lenT為0的時候，我們就已經(jīng)找全了所有的字符。
然后我們就可以對滑動窗口進(jìn)行變化，開始改變i的值，縮小滑動窗口的大小。在這個過程中，利用min以及max來動態(tài)記錄最小子串的下標(biāo)，方便待會兒返回。因為此題的要求不只是返回最小的長度，而是要返回具體的子串。
最后運用substr取子串。
class Solution {
public:
string minWindow(string s, string t) {
int arr[60] = { 0 }; //數(shù)組型哈希表
int i = 0; //窗口左端
int j = 0; //窗口右端
int lenS = s.size(); //記錄S長度
int lenT = t.size(); //記錄T長度
int min = 0; //利用min以及max記錄區(qū)間的下標(biāo)
int max = INT_MAX;
for (int k = 0; k < lenT; k++) //遍歷字符串t，給哈希表賦值
{
arr[t[k] - 'A']++; //字符以ASCII碼形式傳入
}
for (j; j < lenS; j++)
{
if (arr[s[j] - 'A'] -- > 0) //出現(xiàn)t中存在的元素，若大于零，讓lenT-1，并讓哈希表更新，-1
{
lenT--;
}
while (lenT == 0) //當(dāng)lenT為0時，說明以及完全找到所有T中的字符
{
if ((j - i) < (max - min)) //更新區(qū)間，不斷找到最短子串
{
min = i;
max = j;
}
if (++arr[s[i] - 'A'] > 0) //將i指針向前移，縮小窗口，若i此時所指的字符為T中含有的字符，需要更新哈希表以及l(fā)enT
{
//arr[s[i] - 'A']++;
lenT++;
}
i++;
}
}
if (max == INT_MAX) //若max無變動，則表示為找到符合條件的子串
return "";
string res;
res = s.substr(min, max-min+1); //利用substr取子串
return res;
}
};
map型哈希表：
map型總體思路還是類似的，只是換了一個哈希表的載體，更為直觀。
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hs, ht;
for (auto c: t) ht[c] ++ ;
string res;
int cnt = 0;
for (int i = 0, j = 0; i < s.size(); i ++ ) {
hs[s[i]] ++ ;
if (hs[s[i]] <= ht[s[i]]) cnt ++ ;
while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
if (cnt == t.size()) {
if (res.empty() || i - j + 1 < res.size())
res = s.substr(j, i - j + 1);
}
}
return res;
}
};
建立了兩個哈希表，hs哈希表維護(hù)s字符串中滑動窗口各個字符出現(xiàn)的次數(shù)，ht哈希表用于維護(hù)t中字符串出現(xiàn)的次數(shù)。
當(dāng)hs哈希表中包含ht中所有字符時，并且對應(yīng)個數(shù)不小于ht中的個數(shù)時，滑動窗口可行，用cnt記錄已匹配的字符個數(shù)。
往期回顧：
LeetCode977.有序數(shù)組的平方
LeetCode844.比較含退格的字符串
LeetCode283.移動零
LeetCode27.移除元素
LeetCode26.刪除有序數(shù)組中的重復(fù)項
LeetCode209.長度最小的子數(shù)組
LeetCode904. 水果成籃
LeetCode242.有效的字母異位詞
