讀完本文，你可以去力扣拿下如下題目：

76.最小覆蓋子串

567.字符串的排列

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

3.無重復(fù)字符的最長子串

-----------

鑒于前文 二分搜索框架詳解 的那首《二分搜索升天詞》很受好評(píng)，并在民間廣為流傳，成為安睡助眠的一劑良方，今天在滑動(dòng)窗口算法框架中，我再次編寫一首小詩來歌頌滑動(dòng)窗口算法的偉大：

關(guān)于雙指針的快慢指針和左右指針的用法，可以參見前文 雙指針技巧匯總，本文就解決一類最難掌握的雙指針技巧：滑動(dòng)窗口技巧。總結(jié)出一套框架，可以保你閉著眼睛都能寫出正確的解法。

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

說起滑動(dòng)窗口算法，很多讀者都會(huì)頭疼。這個(gè)算法技巧的思路非常簡單，就是維護(hù)一個(gè)窗口，不斷滑動(dòng)，然后更新答案么。LeetCode 上有起碼 10 道運(yùn)用滑動(dòng)窗口算法的題目，難度都是中等和困難。該算法的大致邏輯如下：

int left = 0, right = 0;while (right < s.size()) {`// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 縮小窗口window.remove(s[left]);left++;} }

這個(gè)算法技巧的時(shí)間復(fù)雜度是 O(N)，比字符串暴力算法要高效得多。

其實(shí)困擾大家的，不是算法的思路，而是各種細(xì)節(jié)問題。比如說如何向窗口中添加新元素，如何縮小窗口，在窗口滑動(dòng)的哪個(gè)階段更新結(jié)果。即便你明白了這些細(xì)節(jié)，也容易出 bug，找 bug 還不知道怎么找，真的挺讓人心煩的。

所以今天我就寫一套滑動(dòng)窗口算法的代碼框架，我連再哪里做輸出 debug 都給你寫好了，以后遇到相關(guān)的問題，你就默寫出來如下框架然后改三個(gè)地方就行，還不會(huì)出 bug：

/* 滑動(dòng)窗口算法框架 */ void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; while (right < s.size()) {// c 是將移入窗口的字符char c = s[right];// 右移窗口right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新.../*** debug 輸出的位置 ***/printf("window: [%d, %d)n", left, right);/********************/// 判斷左側(cè)窗口是否要收縮while (window needs shrink) {// d 是將移出窗口的字符char d = s[left];// 左移窗口left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新...}} }

其中兩處 ... 表示的更新窗口數(shù)據(jù)的地方，到時(shí)候你直接往里面填就行了。

而且，這兩個(gè) ... 處的操作分別是右移和左移窗口更新操作，等會(huì)你會(huì)發(fā)現(xiàn)它們操作是完全對(duì)稱的。

說句題外話，我發(fā)現(xiàn)很多人喜歡執(zhí)著于表象，不喜歡探求問題的本質(zhì)。比如說有很多人評(píng)論我這個(gè)框架，說什么散列表速度慢，不如用數(shù)組代替散列表；還有很多人喜歡把代碼寫得特別短小，說我這樣代碼太多余，影響編譯速度，LeetCode 上速度不夠快。

我服了。算法看的是時(shí)間復(fù)雜度，你能確保自己的時(shí)間復(fù)雜度最優(yōu)，就行了。至于 LeetCode 所謂的運(yùn)行速度，那個(gè)都是玄學(xué)，只要不是慢的離譜就沒啥問題，根本不值得你從編譯層面優(yōu)化，不要舍本逐末……

labuladong 公眾號(hào)的重點(diǎn)在于算法思想，你把框架思維了然于心，然后隨你魔改代碼好吧，你高興就好。

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

言歸正傳，下面就直接上四道 LeetCode 原題來套這個(gè)框架，其中第一道題會(huì)詳細(xì)說明其原理，后面四道就直接閉眼睛秒殺了。

本文代碼為 C++ 實(shí)現(xiàn)，不會(huì)用到什么編程方面的奇技淫巧，但是還是簡單介紹一下一些用到的數(shù)據(jù)結(jié)構(gòu)，以免有的讀者因?yàn)檎Z言的細(xì)節(jié)問題阻礙對(duì)算法思想的理解：

unordered_map 就是哈希表（字典），它的一個(gè)方法 count(key) 相當(dāng)于 Java 的 containsKey(key) 可以判斷鍵 key 是否存在。

可以使用方括號(hào)訪問鍵對(duì)應(yīng)的值 map[key]。需要注意的是，如果該 key 不存在，C++ 會(huì)自動(dòng)創(chuàng)建這個(gè) key，并把 map[key] 賦值為 0。

所以代碼中多次出現(xiàn)的 map[key]++ 相當(dāng)于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)。

一、最小覆蓋子串

LeetCode 76 題，Minimum Window Substring，難度 Hard：

就是說要在 S(source) 中找到包含 T(target) 中全部字母的一個(gè)子串，且這個(gè)子串一定是所有可能子串中最短的。

如果我們使用暴力解法，代碼大概是這樣的：

for (int i = 0; i < s.size(); i++)for (int j = i + 1; j < s.size(); j++)if s[i:j] 包含 t 的所有字母:更新答案

思路很直接，但是顯然，這個(gè)算法的復(fù)雜度肯定大于 O(N^2) 了，不好。

滑動(dòng)窗口算法的思路是這樣：

1、我們?cè)谧址?S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引左閉右開區(qū)間 [left, right) 稱為一個(gè)「窗口」。

2、我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此時(shí)，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時(shí)，每次增加 left，我們都要更新一輪結(jié)果。

4、重復(fù)第 2 和第 3 步，直到 right 到達(dá)字符串 S 的盡頭。

這個(gè)思路其實(shí)也不難，第 2 步相當(dāng)于在尋找一個(gè)「可行解」，然后第 3 步在優(yōu)化這個(gè)「可行解」，最終找到最優(yōu)解，也就是最短的覆蓋子串。左右指針輪流前進(jìn)，窗口大小增增減減，窗口不斷向右滑動(dòng)，這就是「滑動(dòng)窗口」這個(gè)名字的來歷。

下面畫圖理解一下，needs 和 window 相當(dāng)于計(jì)數(shù)器，分別記錄 T 中字符出現(xiàn)次數(shù)和「窗口」中的相應(yīng)字符的出現(xiàn)次數(shù)。

初始狀態(tài)：

增加 right，直到窗口 [left, right] 包含了 T 中所有字符：

現(xiàn)在開始增加 left，縮小窗口 [left, right]。

直到窗口中的字符串不再符合要求，left 不再繼續(xù)移動(dòng)。

之后重復(fù)上述過程，先移動(dòng) right，再移動(dòng) left…… 直到 right 指針到達(dá)字符串 S 的末端，算法結(jié)束。

如果你能夠理解上述過程，恭喜，你已經(jīng)完全掌握了滑動(dòng)窗口算法思想?，F(xiàn)在我們來看看這個(gè)滑動(dòng)窗口代碼框架怎么用：

首先，初始化 window 和 need 兩個(gè)哈希表，記錄窗口中的字符和需要湊齊的字符：

unordered_map<char, int> need, window; for (char c : t) need[c]++;

然后，使用 left 和 right 變量初始化窗口的兩端，不要忘了，區(qū)間 [left, right) 是左閉右開的，所以初始情況下窗口沒有包含任何元素：

int left = 0, right = 0; int valid = 0; while (right < s.size()) {// 開始滑動(dòng) }

其中 valid 變量表示窗口中滿足 need 條件的字符個(gè)數(shù)，如果 valid 和 need.size 的大小相同，則說明窗口已滿足條件，已經(jīng)完全覆蓋了串 T。

現(xiàn)在開始套模板，只需要思考以下四個(gè)問題：

1、當(dāng)移動(dòng) right 擴(kuò)大窗口，即加入字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)？

2、什么條件下，窗口應(yīng)該暫停擴(kuò)大，開始移動(dòng) left 縮小窗口？

3、當(dāng)移動(dòng) left 縮小窗口，即移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)？

4、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新？

如果一個(gè)字符進(jìn)入窗口，應(yīng)該增加 window 計(jì)數(shù)器；如果一個(gè)字符將移出窗口的時(shí)候，應(yīng)該減少 window 計(jì)數(shù)器；當(dāng) valid 滿足 need 時(shí)應(yīng)該收縮窗口；應(yīng)該在收縮窗口的時(shí)候更新最終結(jié)果。

下面是完整代碼：

string minWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0;// 記錄最小覆蓋子串的起始索引及長度int start = 0, len = INT_MAX;while (right < s.size()) {// c 是將移入窗口的字符char c = s[right];// 右移窗口right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(c)) {window[c]++;if (window[c] == need[c])valid++;}// 判斷左側(cè)窗口是否要收縮while (valid == need.size()) {// 在這里更新最小覆蓋子串if (right - left < len) {start = left;len = right - left;}// d 是將移出窗口的字符char d = s[left];// 左移窗口left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(d)) {if (window[d] == need[d])valid--;window[d]--;} }}// 返回最小覆蓋子串return len == INT_MAX ?"" : s.substr(start, len); }

需要注意的是，當(dāng)我們發(fā)現(xiàn)某個(gè)字符在 window 的數(shù)量滿足了 need 的需要，就要更新 valid，表示有一個(gè)字符已經(jīng)滿足要求。而且，你能發(fā)現(xiàn)，兩次對(duì)窗口內(nèi)數(shù)據(jù)的更新操作是完全對(duì)稱的。

當(dāng) valid == need.size() 時(shí)，說明 T 中所有字符已經(jīng)被覆蓋，已經(jīng)得到一個(gè)可行的覆蓋子串，現(xiàn)在應(yīng)該開始收縮窗口了，以便得到「最小覆蓋子串」。

移動(dòng) left 收縮窗口時(shí)，窗口內(nèi)的字符都是可行解，所以應(yīng)該在收縮窗口的階段進(jìn)行最小覆蓋子串的更新，以便從可行解中找到長度最短的最終結(jié)果。

至此，應(yīng)該可以完全理解這套框架了，滑動(dòng)窗口算法又不難，就是細(xì)節(jié)問題讓人煩得很。以后遇到滑動(dòng)窗口算法，你就按照這框架寫代碼，保準(zhǔn)沒有 bug，還省事兒。

下面就直接利用這套框架秒殺幾道題吧，你基本上一眼就能看出思路了。

二、字符串排列

LeetCode 567 題，Permutation in String，難度 Medium：

注意哦，輸入的 s1 是可以包含重復(fù)字符的，所以這個(gè)題難度不小。

這種題目，是明顯的滑動(dòng)窗口算法，相當(dāng)給你一個(gè) S 和一個(gè) T，請(qǐng)問你 S 中是否存在一個(gè)子串，包含 T 中所有字符且不包含其他字符？

首先，先復(fù)制粘貼之前的算法框架代碼，然后明確剛才提出的 4 個(gè)問題，即可寫出這道題的答案：

// 判斷 s 中是否存在 t 的排列 bool checkInclusion(string t, string s) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0;while (right < s.size()) {char c = s[right];right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(c)) {window[c]++;if (window[c] == need[c])valid++;}// 判斷左側(cè)窗口是否要收縮while (right - left >= t.size()) {// 在這里判斷是否找到了合法的子串if (valid == need.size())return true;char d = s[left];left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(d)) {if (window[d] == need[d])valid--;window[d]--;}}}// 未找到符合條件的子串return false; }

對(duì)于這道題的解法代碼，基本上和最小覆蓋子串一模一樣，只需要改變兩個(gè)地方：

1、本題移動(dòng) left 縮小窗口的時(shí)機(jī)是窗口大小大于 t.size() 時(shí)，應(yīng)為排列嘛，顯然長度應(yīng)該是一樣的。

2、當(dāng)發(fā)現(xiàn) valid == need.size() 時(shí)，就說明窗口中就是一個(gè)合法的排列，所以立即返回 true。

至于如何處理窗口的擴(kuò)大和縮小，和最小覆蓋子串完全相同。

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

三、找所有字母異位詞

這是 LeetCode 第 438 題，Find All Anagrams in a String，難度 Medium：

呵呵，這個(gè)所謂的字母異位詞，不就是排列嗎，搞個(gè)高端的說法就能糊弄人了嗎？相當(dāng)于，輸入一個(gè)串 S，一個(gè)串 T，找到 S 中所有 T 的排列，返回它們的起始索引。

直接默寫一下框架，明確剛才講的 4 個(gè)問題，即可秒殺這道題：

vector<int> findAnagrams(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0;vector<int> res; // 記錄結(jié)果while (right < s.size()) {char c = s[right];right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}// 判斷左側(cè)窗口是否要收縮while (right - left >= t.size()) {// 當(dāng)窗口符合條件時(shí)，把起始索引加入 resif (valid == need.size())res.push_back(left);char d = s[left];left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.count(d)) {if (window[d] == need[d])valid--;window[d]--;}}}return res; }

跟尋找字符串的排列一樣，只是找到一個(gè)合法異位詞（排列）之后將起始索引加入 res 即可。

四、最長無重復(fù)子串

這是 LeetCode 第 3 題，Longest Substring Without Repeating Characters，難度 Medium：

這個(gè)題終于有了點(diǎn)新意，不是一套框架就出答案，不過反而更簡單了，稍微改一改框架就行了：

int lengthOfLongestSubstring(string s) {unordered_map<char, int> window;int left = 0, right = 0;int res = 0; // 記錄結(jié)果while (right < s.size()) {char c = s[right];right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新window[c]++;// 判斷左側(cè)窗口是否要收縮while (window[c] > 1) {char d = s[left];left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新window[d]--;}// 在這里更新答案res = max(res, right - left);}return res; }

~
這就是變簡單了，連 need 和 valid 都不需要，而且更新窗口內(nèi)數(shù)據(jù)也只需要簡單的更新計(jì)數(shù)器 window 即可。

當(dāng) window[c] 值大于 1 時(shí)，說明窗口中存在重復(fù)字符，不符合條件，就該移動(dòng) left 縮小窗口了嘛。

唯一需要注意的是，在哪里更新結(jié)果 res 呢？我們要的是最長無重復(fù)子串，哪一個(gè)階段可以保證窗口中的字符串是沒有重復(fù)的呢？

這里和之前不一樣，要在收縮窗口完成后更新 res，因?yàn)榇翱谑湛s的 while 條件是存在重復(fù)元素，換句話說收縮完成后一定保證窗口中沒有重復(fù)嘛。

五、最后總結(jié)

建議背誦并默寫這套框架，順便背誦一下文章開頭的那首詩。以后就再也不怕子串、子數(shù)組問題了好吧。

數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)指南

動(dòng)態(tài)規(guī)劃解題框架

回溯算法解題框架

為了學(xué)會(huì)二分搜索，我寫了首詩

一文搞懂 session 和 cookie 是什么

一文搞懂非對(duì)稱加密/背包交換算法/數(shù)字簽名/證書

Linux 進(jìn)程、線程、文件描述符的底層原理

一起刷題學(xué)習(xí) Git/SQL/正則表達(dá)式

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！

總結(jié)

以上是生活随笔為你收集整理的列表左右箭头滑动_我写了一套框架，把滑动窗口算法变成了默写题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。