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

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

intleft=0,right=0; while(right

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

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

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

/*滑動(dòng)窗口算法框架*/ voidslidingWindow(strings,stringt){ unordered_mapneed,window; for(charc:t)need[c]++; intleft=0,right=0; intvalid=0; while(right

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

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

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

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

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

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

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

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

可以使用方括號(hào)訪問(wèn)鍵對(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，我?guī)Т蠹铱纯此降子卸郒ard：

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

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

for(inti=0;i

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

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

1、我們?cè)谧址甋中使用雙指針中的左右指針技巧，初始化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è)名字的來(lái)歷。

下面畫圖理解一下，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ù)上述過(guò)程，先移動(dòng)right，再移動(dòng)left…… 直到right指針到達(dá)字符串S的末端，算法結(jié)束。

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

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

unordered_mapneed,window; for(charc:t)need[c]++;

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

intleft=0,right=0; intvalid=0; while(right

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

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

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é)果。

下面是完整代碼：

stringminWindow(strings,stringt){ unordered_mapneed,window; for(charc:t)need[c]++; intleft=0,right=0; intvalid=0; //記錄最小覆蓋子串的起始索引及長(zhǎng)度 intstart=0,len=INT_MAX; while(right

需要注意的是，當(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í)，說(shuō)明T中所有字符已經(jīng)被覆蓋，已經(jīng)得到一個(gè)可行的覆蓋子串，現(xiàn)在應(yīng)該開始收縮窗口了，以便得到「最小覆蓋子串」。

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

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

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

二、字符串排列

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

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

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

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

//判斷s中是否存在t的排列 boolcheckInclusion(stringt,strings){ unordered_mapneed,window; for(charc:t)need[c]++; intleft=0,right=0; intvalid=0; while(right=t.size()){ //在這里判斷是否找到了合法的子串 if(valid==need.size()) returntrue; chard=s[left]; left++; //進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新 if(need.count(d)){ if(window[d]==need[d]) valid--; window[d]--; } } } //未找到符合條件的子串 returnfalse; }

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

1、本題移動(dòng)left縮小窗口的時(shí)機(jī)是窗口大小大于t.size()時(shí)，因?yàn)榕帕新?，顯然長(zhǎng)度應(yīng)該是一樣的。

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

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

三、找所有字母異位詞

這是 LeetCode 第 438 題，F(xiàn)ind All Anagrams in a String，難度 Medium：

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

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

vectorfindAnagrams(strings,stringt){ unordered_mapneed,window; for(charc:t)need[c]++; intleft=0,right=0; intvalid=0; vectorres;//記錄結(jié)果 while(right=t.size()){ //當(dāng)窗口符合條件時(shí)，把起始索引加入res if(valid==need.size()) res.push_back(left); chard=s[left]; left++; //進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新 if(need.count(d)){ if(window[d]==need[d]) valid--; window[d]--; } } } returnres; }

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

四、最長(zhǎng)無(wú)重復(fù)子串

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

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

intlengthOfLongestSubstring(strings){ unordered_mapwindow; intleft=0,right=0; intres=0;//記錄結(jié)果 while(right1){ chard=s[left]; left++; //進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新 window[d]--; } //在這里更新答案 res=max(res,right-left); } returnres; }

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

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

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

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

五、最后總結(jié)

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

我覺得吧，能夠看到這的都是高手，要么就是在成為高手的路上。有了框架，任他窗口怎么滑，東哥這波車開得依然穩(wěn)如老狗，「在看」安排一下。