前言

本專欄上一篇博客，帶著大家從認識滑動窗口到慢慢熟悉
相信大家對滑動窗口已經有了大概的認識
其實主要就是抓住——一段連續的區間
今天來學習一些滑動窗口進階的題目
fellow me

水果成籃

思路

一開始看到這個題目，一段連續的區間，想到了滑動窗口
然后就想著怎么維護窗口，每次更新到新的水果種類就要，開始對left++，然后處理數據
其實是有點麻煩的，但是經過半個多小時的調試，最后還是ac了
思路：每次更新兩個種類的水果，x，y，如果下一個水果的種類不相符合，就更新新的x，y
這個時候 right - 1 和 right 所對應的水果就是新的兩種，然后就是處理從 left 到 right - 1這段區間
符合條件的情況， 也就是 從right - 1 一直往前走，到與 right - 1 所對應種類不同的水果，然后再更新結果
在反復進窗口，維護窗口，出窗口

代碼如下 ：

class Solution
{
public:int totalFruit(vector<int>& fruits){int ans = 0;int n = fruits.size();int x = fruits[0], y = fruits[0];if (n == 1)return 1;int left = 0, right = 1;for (; right < n; right++){if (fruits[right] != x && fruits[right] != y)  // 和前面確定的水果種類{y = fruits[right - 1];		//  更新新的水果種類  x = fruits[right];int i = right - 1;if (i != left)  // left  到  right - 1  區間  {while (fruits[i] == y && i > left)  //  i一直靠近left  直到種類不同{i--;}if (i == left && y != fruits[left])  //  更新  left 的指向left++;else if (i != left)left = i + 1;}}ans = max(ans, right - left + 1);//    更新結果}return ans;}
};

后面又想到了一種思路：
就是用哈希來統計種類數量，哈希相對于前面的那種方法還是簡單的
就是把兩個種類的水果放入哈希表，然后right++ 水果進窗口，如果哈希表的水果種類大于2
就從左側 left 開始逐步出窗口，直到哈希表種類等于2，然后更新結果

代碼如下：

class Solution
{
public:int totalFruit(vector<int>& f){unordered_map<int, int> hash; // 統計窗口內出現了多少種水果int ret = 0;for (int left = 0, right = 0; right < f.size(); right++){hash[f[right]]++; // 進窗口while (hash.size() > 2) // 判斷{// 出窗口hash[f[left]]--;if (hash[f[left]] == 0)hash.erase(f[left]);left++;}ret = max(ret, right - left + 1);}return ret;}
};

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

思路

看到又是一段連續的區間，就想到了滑動窗口
這一題 p 的異位詞，說白了就是包含了 p 的所有字母，不管先后順序
想到上一題用哈希優化的爽快，這題好像也可以用哈希來解
把 p 中字符都用哈希統計頻次，然后在遍歷 s 時，進窗口，維護窗口，出窗口
每次進入窗口，就用哈希統計出現次數，只要沒有到達次數上限，就進窗口
如果進入窗口的字符數量大于了 p 的長度，就維護窗口，從left開始往右開始出窗口
在每一次統計進入窗口的數量時，都比較一下 p 的字符個數，如果進入窗口的字符個數等于 p的個數大小相等，就更新結果

代碼如下：

class Solution
{
public:vector<int> findAnagrams(string s, string p){vector<int> ret;int hash1[26] = { 0 }; // 統計字符串 p 中每個字符出現的個數for(auto ch : p) hash1[ch - 'a']++;int hash2[26] = { 0 }; // 統計窗口里面的每一個字符出現的個數int m = p.size();for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];// 進窗口 + 維護 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++;if(right - left + 1 > m) // 判斷{char out = s[left++];// 出窗口 + 維護 countif(hash2[out - 'a']-- <= hash1[out - 'a']) count--;}// 更新結果if(count == m) ret.push_back(left);}return ret;}
};

---

下面就上難度了嗷~~~~

串聯所有單詞的子串

思路

這個題目看起來很難，其實一點也不簡單，看到困難的標簽就讓人望而生畏
但其實也沒有想象的那么難，慢慢抽絲剝繭，其實也能拿下

看到這里，其實就想到了上一題的那個字母異位詞，本題是說所有單詞都包含，然后不管順序
上一題是——所有字母都包含，然后不管順序，我們不妨試試上一題的思路呢
首先要解決的就是把單詞抽象變成字符，我們可以定義一個 string，映射 int 的 哈希表，這個問題就迎刃而解了
下一個問題就是怎么才能知道哪個是單詞的開頭字母呢？？又怎么在 s 中遍歷單詞然后進窗口呢？？

我又看到了這個條件，雪中送炭，所有單詞長度相等，那豈不是起飛了，就讓 right 每次遍歷 += 單詞長度就好了
這些都處理好了，最后一個問題就是，我怎么知道哪個字符是單詞的第一個字母，錯亂了怎么辦，那不是gg
我們只需要在外面套一層for循環，從0到單詞的長度，這段區間都做一次滑動窗口就好啦
核心問題都解決了，剩下的就是一些細節處理問題了
話不多說，這些都解決了，開始執行代碼：

class Solution 
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1; // 保存 words 里面所有單詞的頻次for (auto& c : words)hash1[c]++;int len = words[0].size(), m = words.size();for (int i = 0; i < len; i++) // 執行 len 次{unordered_map<string, int> hash2; // 維護窗口內單詞的頻次for (int left = i, right = i, count = 0; right + len <= s.size();right += len) {// 進窗口 + 維護 countstring in = s.substr(right, len);hash2[in]++;if (hash1.count(in) && hash2[in] <= hash1[in])count++;// 判斷if (right - left + 1 > len * m) {// 出窗口 + 維護 countstring out = s.substr(left, len);if (hash1.count(out) && hash2[out] <= hash1[out])count--;hash2[out]--;left += len;}// 更新結果if (count == m)ret.push_back(left);}}return ret;}
};

其實hard題也是由一個一個小問題糅合起來的，解決核心問題，其實也沒有那么難
慢慢啃下來，還是有成就感的 come on

最小覆蓋子串

思路

又又又是一段連續的區間，來吧來吧，滑動窗口，滑動窗口

這道題不是上一題的恰好涵蓋所有字符了，要返回的是最小子串，也就是能包含其他的
但是經過前面題目的磨礪，我感覺好像自己有點門道了
思路：用哈希1統計字符串 t 的每一個字符的頻次，還有種類
構造一個新的哈希2，然后遍歷 s 字符串，每個字符都統計到新的哈希表
當這個字符的頻次和 哈希1中統計的字符頻次相等時，種類數++
當種類數和哈希1種類數相等時，維護窗口，更新結果
大致思路就差不多是這樣，來執行代碼吧

class Solution 
{
public: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--; // 出窗口 + 維護 count}}if (begin == -1)return "";elsereturn s.substr(begin, minlen);}
};

這個困難也拿下啦，滑動窗口和哈希一起用感覺有點爽，絕佳組合

總結

滑動窗口的核心在于維護一段連續區間，通過哈希表優化統計與比較過程。面對不同問題需靈活調整：
哈希表記錄元素頻次，快速判斷窗口合法性（如水果種類、異位詞）
雙指針動態伸縮窗口，確保時間復雜度為O(N)
多層循環處理定長元素（如單詞串聯），覆蓋所有起點情況
種類與頻次匹配時更新結果，最小子串問題需全局記錄最優解
掌握滑動窗口+哈希的組合，能高效解決子串、子數組等連續區間問題，突破Hard瓶頸

今天的內容就到這里啦，不要走開，小編持續更新中~~~~