目錄

水果成籃

解題思路

代碼實(shí)現(xiàn)

找到字符串中所有字母異位詞

解題思路

代碼實(shí)現(xiàn)

串聯(lián)所有單詞的子串

解題思路

代碼實(shí)現(xiàn)

最小覆蓋子串

解題思路

代碼實(shí)現(xiàn)

---

水果成籃

題目鏈接：904. 水果成籃

題目描述：
你正在探訪一家農(nóng)場(chǎng)，農(nóng)場(chǎng)從左到右種植了一排果樹。這些樹用一個(gè)整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果種類。你想要盡可能多地收集水果，但是有一些規(guī)則：

• 你有兩個(gè)籃子，每個(gè)籃子只能裝一種類型的水果，籃子的容量無限制。
• 你可以選擇任意一棵樹開始采摘，但必須從這棵樹開始依次向右采摘每棵樹上的水果。
• 一旦遇到某棵樹上的水果不符合籃子中的水果種類，你必須停止采摘。

返回你能采摘的最多的水果數(shù)量。

解題思路

解法：滑動(dòng)窗口+哈希

根據(jù)題目要求，所求問題其實(shí)就是找一段最多只含兩個(gè)不同元素的最長(zhǎng)子區(qū)間，我們使用滑動(dòng)窗口+哈希解決。

有一點(diǎn)值得注意，fruits[i] 是第 i 棵樹上的水果種類，不是種類數(shù)。

具體過程如下：

• 1.初始化哈希表 hash，左右指針 left 和 right，記錄結(jié)果的變量 ret。
• 2.right 向右遍歷數(shù)組，將 right 位置的水果加入哈希表，統(tǒng)計(jì)頻次。
• 如果哈希表的大小超過2，讓left++并同時(shí)更新哈希表，直至哈希表的大小不超過2。
• 3.更新結(jié)果 ret。
• 4重復(fù)上述過程，直到 right 遍歷完數(shù)組。

代碼實(shí)現(xiàn)

1.使用unordered_map作為hash表

class Solution {
public:int totalFruit(vector<int>& fruits) {// 統(tǒng)計(jì)滑動(dòng)窗口內(nèi)水果的種類和數(shù)量unordered_map<int, int> hash;int n = fruits.size(), ret = 0;for(int left = 0, right = 0; right < n; right++){//進(jìn)窗口，將水果加入hash表hash[fruits[right]]++;//若水果種類超過2，收縮窗口直到種類不超過2while(hash.size() > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0) hash.erase(fruits[left]);left++;}//更新結(jié)果ret = max(ret, right - left + 1);}return ret;}
};

?2.使用數(shù)組模擬hash表

題目其實(shí)有提到?fruits[i] 的范圍，所以我們不必真的使用unordered_map作為hash表，使用數(shù)組模擬即可，這樣雖然會(huì)浪費(fèi)空間，但是提高了效率。

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100000] = { 0 };//cnt用于統(tǒng)計(jì)hash表的水果的種類個(gè)數(shù)int n = fruits.size(), ret = 0, cnt = 0;for(int left = 0, right = 0; right < n; right++){hash[fruits[right]]++;if(hash[fruits[right]] == 1) cnt++;while(cnt > 2){hash[fruits[left]]--;if(hash[fruits[left++]] == 0) cnt--;}ret = max(ret, right - left + 1);}return ret;}
};

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

---

找到字符串中所有字母異位詞

題目鏈接：438. 找到字符串中所有字母異位詞

題目描述：

給定兩個(gè)字符串 s 和 p，找到 s 中所有 p 的?異位詞?的子串，返回這些子串的起始索引。順序可以不考慮。

異位詞是指由相同字母重排列形成的字符串（包括相同的字符串）。

解題思路

解法：滑動(dòng)窗口 + 哈希

因?yàn)?strong>字符串 p 的異位詞的長(zhǎng)度一定于字符串 p 的長(zhǎng)度相等，所以我們可以在字符串 s 中使用與字符串 p 等長(zhǎng)度的滑動(dòng)窗口來求解。

我們可以使用兩個(gè)大小為26的數(shù)組來模擬哈希表，用于統(tǒng)計(jì)窗口內(nèi)的字母頻次和字符串s的字母頻次，當(dāng)比較得到兩個(gè)哈希表相等時(shí)，說明滑動(dòng)窗口中每種字母的數(shù)量與字符 p 每種字母的數(shù)量相同，窗口內(nèi)的字符是字符 p 的一個(gè)異位詞，此時(shí)記錄窗口起始索引。

具體過程如下：

• 1.初始化 left 和 right 指針來維護(hù)滑動(dòng)窗口，兩個(gè)大小為26的數(shù)組 hash1 和 hash2 來模擬哈希表，記錄字符串 p 的字母頻次和窗口字母頻次。

• 2.right 向右遍歷數(shù)組
• right 位置的字母入窗口，將其加入哈希表。
• 當(dāng)滑動(dòng)窗口長(zhǎng)度大于字符串 p 的長(zhǎng)度時(shí)，left++，將窗口左側(cè)字母移除同時(shí)更新其在哈希表的頻次。

• 3.更新結(jié)果，當(dāng) hash1 與 hash2 相等時(shí)，記錄窗口起始索引。

注意：判斷兩個(gè) hash 表是否相等的時(shí)間復(fù)雜度較高，效率較低。故我們要優(yōu)化更新結(jié)果的判斷條件（兩個(gè)哈希表相等），我們可以來使用一個(gè)變量 cnt 記錄窗口內(nèi)的字母相較于字符串 p 的有效字符的數(shù)量，并在入窗口和窗口時(shí)維護(hù) cnt，這樣更新結(jié)果時(shí)，只需判斷 cnt 是否等于字符串 p 的長(zhǎng)度就可以知道窗口字符是否是字符串 p 的異位詞。

解釋下有效字符的數(shù)量，其實(shí)就是讓窗口的組成字母盡可能接近字符 p ，當(dāng)有效字符的數(shù)量等于字符 p 的長(zhǎng)度，就說明了窗口的字母頻次與字符 p 的字母頻次相等，這也是比較兩個(gè)統(tǒng)計(jì)字母頻次的哈希表相等的本質(zhì)，cnt 間接完成了這個(gè)任務(wù)。

代碼實(shí)現(xiàn)

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int n = s.size(), m = p.size();//統(tǒng)計(jì)p字符串中每個(gè)字母出現(xiàn)的個(gè)數(shù)int hash1[26] = { 0 };for(auto ch : p) hash1[ch - 'a']++;//統(tǒng)計(jì)窗口中每個(gè)字母出現(xiàn)的個(gè)數(shù)int hash2[26] = { 0 };//統(tǒng)計(jì)窗口中有效字符的數(shù)量int cnt = 0;for(int left = 0, right = 0; right < n; right++){//進(jìn)窗口 + 維護(hù)cntchar in = s[right];hash2[in - 'a']++;if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++;//窗口長(zhǎng)度大于字符串p的長(zhǎng)度，窗口左端字母出窗口，//并更新cnt和哈希表if(right - left + 1 > m){char out = s[left++];//出窗口 + 維護(hù)cntif(hash2[out - 'a'] <= hash1[out - 'a']) cnt--;hash2[out - 'a']--;}//更新結(jié)果if(cnt == m) ret.push_back(left);}return ret;}
};

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

---

串聯(lián)所有單詞的子串

題目鏈接：30. 串聯(lián)所有單詞的子串

題目描述：

給定一個(gè)字符串 s 和一個(gè)字符串?dāng)?shù)組 words，words 中所有字符串的長(zhǎng)度相同。s 中的 串聯(lián)子串 是指包含 words 中所有字符串以任意順序排列連接起來的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串聯(lián)子串，而 "acdbef" 不是串聯(lián)子串，因?yàn)樗皇?words 排列的連接。

返回所有串聯(lián)子串在 s 中的開始索引，順序可以不考慮。

解題思路

解法：滑動(dòng)窗口 + 哈希表

這道題就是找到字符串中所有字母異位詞的升級(jí)版，從原來處理單個(gè)字符變成了處理單個(gè)單詞，我們只需要將 words 的單詞看成單個(gè)字母就行了，然后用滑動(dòng)窗口 + 哈希表解決。

具體過程：

1.用哈希表 hash1 記錄 words 中每個(gè)單詞的頻次。

2.遍歷字符串 s ，并用哈希表 hash2 來維護(hù)滑動(dòng)窗口內(nèi)的單詞頻次，注意每次增加窗口的大小為單詞的長(zhǎng)度。

3.當(dāng)窗口大小大于所有單詞的總長(zhǎng)度時(shí)，出窗口和更新 hash2 。

4.當(dāng) hash1 和 hash2 兩個(gè)哈希表相等時(shí)，更新結(jié)果。

判斷兩個(gè)哈希表是否相等消耗較大，用 count 來優(yōu)化，count 統(tǒng)計(jì)滑動(dòng)窗口內(nèi)有效單詞的個(gè)數(shù)。當(dāng) count 與 words 的單詞個(gè)數(shù)相等時(shí)，說明找到了符合條件的一個(gè)窗口。

代碼實(shí)現(xiàn)

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;for(auto& e : words) hash1[e]++;int len = words[0].size(), m = words.size(), n = s.size();//執(zhí)行l(wèi)en次滑動(dòng)窗口for(int i = 0; i < len; ++i){unordered_map<string, int> hash2;for(int left = i, right = i, count = 0; right <= n - len; right += len){//進(jìn)窗口+維護(hù)countstring in(s.begin() + right, s.begin() + right + len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) count++;//判斷+出窗口+維護(hù)countif(right - left + 1 > m * len){string out(s.begin() + left, s.begin() + left + len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}//更新結(jié)果if(count == m)ret.push_back(left);}}return ret;}
};

1.執(zhí)行 len 次滑動(dòng)窗口（len 是單詞長(zhǎng)度）：由 s 字符串的長(zhǎng)度不一定是單詞長(zhǎng)度的整數(shù)倍，需要執(zhí)行 len 滑動(dòng)窗口來保證答案的完整性。

2.注意 right 的范圍，right 最后一次執(zhí)行循環(huán)的位置應(yīng)該是在 n - len 處。

時(shí)間復(fù)雜度：O( n * len)，其中 n 是字符串 s 的長(zhǎng)度，需要 len 次滑動(dòng)窗口，每次遍歷一次 s。

空間復(fù)雜度：O(m * len)，m 是單詞個(gè)數(shù)，每次滑動(dòng)窗口都需要用一個(gè)哈希表來存儲(chǔ)單詞頻次。

---

最小覆蓋子串

題目鏈接：76. 最小覆蓋子串

題目描述：

給你一個(gè)字符串 s 和一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果?s?中不存在這樣的子串，則返回空字符串?""。

注意：

• 對(duì)于?t?中重復(fù)的字符，最小子串中該字符數(shù)量必須不少于?t?中的字符數(shù)量。
• 如果存在這樣的子串，答案是唯一的。

解題思路

解法：滑動(dòng)窗口+哈希

根據(jù)題目，我們直接根據(jù)暴力解法來優(yōu)化，就得到滑動(dòng)窗口+哈希的解題方法。

具體過程如下：

1.利哈希表 hash1 來統(tǒng)計(jì)字符串 t 中每個(gè)字符出現(xiàn)的頻次。

2.使用滑動(dòng)窗口遍歷字符串 s ，并用哈希表 hash2 來統(tǒng)計(jì)窗口中字符頻次。

3.當(dāng)窗口的字符頻次滿足要求時(shí)，更新結(jié)果，然后收縮窗口，直到窗口字符頻次不滿足要求。

注意：這里判斷窗口的字符頻次滿足要求不是判斷兩個(gè)哈希表是否相等，而是 hash1 的字符頻次要完整的出現(xiàn)在?hash2 中，hash1 中可以出現(xiàn)除字符串 t 中的字符以外的字符頻次。也就是說，窗口內(nèi)只要完整出現(xiàn)字符串 t? 的所有字符即可（字符種類及其對(duì)應(yīng)的頻次）。

我們這里還是利用 count 來完成判斷，這里的 count 統(tǒng)計(jì)的時(shí)有效字符的種類，只有 t 中的單個(gè)字符在窗口內(nèi)出現(xiàn)的頻次與在 t 中完全一樣，count 才自增1，同理，頻次不相等時(shí)就自減 1，當(dāng) count 與 t 中字符種類數(shù)相同時(shí)，說明找到一個(gè)符合條件的覆蓋字串，更新結(jié)果。

代碼實(shí)現(xiàn)

class Solution {
public:string minWindow(string s, string t) {string ret;//hash1統(tǒng)計(jì)t字符頻次和計(jì)算hash1的大小，hash1size統(tǒng)計(jì)t的字符種類int hash1[128] = { 0 }, hash1size = 0;for(auto e : t) if(hash1[e]++ == 0) hash1size++;//hash2統(tǒng)計(jì)窗口字符頻次int hash2[128] = { 0 };int len = INT_MAX, start = 0;//count統(tǒng)計(jì)有效字符的種類for(int left = 0, right = 0, count = 0; right < s.size(); right++){//進(jìn)窗口 + 維護(hù)countchar in = s[right];if(++hash2[in] == hash1[in]) count++;//判斷while(count == hash1size){//更新結(jié)果if(right - left + 1 < len){len = right - left + 1;start = left;}//出窗口+維護(hù)countchar out = s[left++];if(hash2[out]-- == hash1[out]) count--;}}ret = len == INT_MAX ? "" : s.substr(start, len);return ret;}
};

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

---

拜拜，下期再見😏

摸魚ing😴?🎞