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

76.最小覆蓋子串

567.字串的排列

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

3.無重複字元的最長子串

-----------

鑑於前文 二分搜尋框架詳解 的那首《二分搜尋昇天詞》很受好評，並在民間廣為流傳，成為安睡助眠的一劑良方，今天在滑動視窗演算法框架中，我再次編寫一首小詩來歌頌滑動視窗演算法的偉大：

關於雙指標的快慢指標和左右指標的用法，可以參見前文 雙指標技巧彙總，本文就解決一類最難掌握的雙指標技巧：滑動視窗技巧。總結出一套框架，可以保你閉著眼睛都能寫出正確的解法。

說起滑動視窗演算法，很多讀者都會頭疼。這個演算法技巧的思路非常簡單，就是維護一個視窗，不斷滑動，然後更新答案麼。LeetCode 上有起碼 10 道運用滑動視窗演算法的題目，難度都是中等和困難。該演算法的大致邏輯如下：

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

這個演算法技巧的時間複雜度是 O(N)，比字串暴力演算法要高效得多。

其實困擾大家的，不是演算法的思路，而是各種細節問題。比如說如何向視窗中新增新元素，如何縮小視窗，在視窗滑動的哪個階段更新結果。即便你明白了這些細節，也容易出 bug，找 bug 還不知道怎麼找，真的挺讓人心煩的。

所以今天我就寫一套滑動視窗演算法的程式碼框架，我連再哪裡做輸出 debug 都給你寫好了，以後遇到相關的問題，你就默寫出來如下框架然後改三個地方就行，還不會出 bug：

/* 滑動視窗演算法框架 */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++;        // 進行視窗內資料的一系列更新        ...        /*** debug 輸出的位置 ***/        printf("window: [%d, %d)\n", left, right);        /********************/                // 判斷左側視窗是否要收縮        while (window needs shrink) {            // d 是將移出視窗的字元            char d = s[left];            // 左移視窗            left++;            // 進行視窗內資料的一系列更新            ...        }    }}

其中兩處 ... 表示的更新視窗資料的地方，到時候你直接往裡面填就行了。

而且，這兩個 ... 處的操作分別是右移和左移視窗更新操作，等會你會發現它們操作是完全對稱的。

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

本文程式碼為 C++ 實現，不會用到什麼程式設計方面的奇技淫巧，但是還是簡單介紹一下一些用到的資料結構，以免有的讀者因為語言的細節問題阻礙對演算法思想的理解：

unordered_map 就是雜湊表（字典），它的一個方法 count(key) 相當於 Java 的 containsKey(key) 可以判斷鍵 key 是否存在。

可以使用方括號訪問鍵對應的值 map[key]。需要注意的是，如果該 key 不存在，C++ 會自動建立這個 key，並把 map[key] 賦值為 0。

所以程式碼中多次出現的 map[key]++ 相當於 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)。

一、最小覆蓋子串

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

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

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

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

思路很直接，但是顯然，這個演算法的複雜度肯定大於 O(N^2) 了，不好。

滑動視窗演算法的思路是這樣：

1、我們在字串 S 中使用雙指標中的左右指標技巧，初始化 left = right = 0，把索引左閉右開區間 [left, right) 稱為一個「視窗」。

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

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

4、重複第 2 和第 3 步，直到 right 到達字串 S 的盡頭。

這個思路其實也不難，第 2 步相當於在尋找一個「可行解」，然後第 3 步在最佳化這個「可行解」，最終找到最優解，也就是最短的覆蓋子串。左右指標輪流前進，視窗大小增增減減，視窗不斷向右滑動，這就是「滑動視窗」這個名字的來歷。

下面畫圖理解一下，needs 和 window 相當於計數器，分別記錄 T 中字元出現次數和「視窗」中的相應字元的出現次數。

初始狀態：

增加 right，直到視窗 [left, right) 包含了 T 中所有字元：

現在開始增加 left，縮小視窗 [left, right)。

直到視窗中的字串不再符合要求，left 不再繼續移動。

之後重複上述過程，先移動 right，再移動 left…… 直到 right 指標到達字串 S 的末端，演算法結束。

如果你能夠理解上述過程，恭喜，你已經完全掌握了滑動視窗演算法思想。現在我們來看看這個滑動視窗程式碼框架怎麼用：

首先，初始化 window 和 need 兩個雜湊表，記錄視窗中的字元和需要湊齊的字元：

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

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

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

其中 valid 變量表示視窗中滿足 need 條件的字元個數，如果 valid 和 need.size 的大小相同，則說明視窗已滿足條件，已經完全覆蓋了串 T。

現在開始套模板，只需要思考以下四個問題：

1、當移動 right 擴大視窗，即加入字元時，應該更新哪些資料？

2、什麼條件下，視窗應該暫停擴大，開始移動 left 縮小視窗？

3、當移動 left 縮小視窗，即移出字元時，應該更新哪些資料？

4、我們要的結果應該在擴大視窗時還是縮小視窗時進行更新？

如果一個字元進入視窗，應該增加 window 計數器；如果一個字元將移出視窗的時候，應該減少 window 計數器；當 valid 滿足 need 時應該收縮視窗；應該在收縮視窗的時候更新最終結果。

下面是完整程式碼：

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++;        // 進行視窗內資料的一系列更新        if (need.count(c)) {            window[c]++;            if (window[c] == need[c])                valid++;        }​        // 判斷左側視窗是否要收縮        while (valid == need.size()) {            // 在這裡更新最小覆蓋子串            if (right - left < len) {                start = left;                len = right - left;            }            // d 是將移出視窗的字元            char d = s[left];            // 左移視窗            left++;            // 進行視窗內資料的一系列更新            if (need.count(d)) {                if (window[d] == need[d])                    valid--;                window[d]--;            }                            }    }    // 返回最小覆蓋子串    return len == INT_MAX ?        "" : s.substr(start, len);}

需要注意的是，當我們發現某個字元在 window 的數量滿足了 need 的需要，就要更新 valid，表示有一個字元已經滿足要求。而且，你能發現，兩次對視窗內資料的更新操作是完全對稱的。

當 valid == need.size() 時，說明 T 中所有字元已經被覆蓋，已經得到一個可行的覆蓋子串，現在應該開始收縮視窗了，以便得到「最小覆蓋子串」。

移動 left 收縮視窗時，視窗內的字元都是可行解，所以應該在收縮視窗的階段進行最小覆蓋子串的更新，以便從可行解中找到長度最短的最終結果。

至此，應該可以完全理解這套框架了，滑動視窗演算法又不難，就是細節問題讓人煩得很。以後遇到滑動視窗演算法，你就按照這框架寫程式碼，保準沒有 bug，還省事兒。

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

二、字串排列

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

注意哦，輸入的 s1 是可以包含重複字元的，所以這個題難度不小。

這種題目，是明顯的滑動視窗演算法，相當給你一個 S 和一個 T，請問你 S 中是否存在一個子串，包含 T 中所有字元且不包含其他字元？

首先，先複製貼上之前的演算法框架程式碼，然後明確剛才提出的 4 個問題，即可寫出這道題的答案：

// 判斷 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++;        // 進行視窗內資料的一系列更新        if (need.count(c)) {            window[c]++;            if (window[c] == need[c])                valid++;        }​        // 判斷左側視窗是否要收縮        while (right - left >= t.size()) {            // 在這裡判斷是否找到了合法的子串            if (valid == need.size())                return true;            char d = s[left];            left++;            // 進行視窗內資料的一系列更新            if (need.count(d)) {                if (window[d] == need[d])                    valid--;                window[d]--;            }        }    }    // 未找到符合條件的子串    return false;}

對於這道題的解法程式碼，基本上和最小覆蓋子串一模一樣，只需要改變兩個地方：

1、本題移動 left 縮小視窗的時機是視窗大小大於 t.size() 時，應為排列嘛，顯然長度應該是一樣的。

2、當發現 valid == need.size() 時，就說明視窗中就是一個合法的排列，所以立即返回 true。

至於如何處理視窗的擴大和縮小，和最小覆蓋子串完全相同。

三、找所有字母異位詞

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

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

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

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; // 記錄結果    while (right < s.size()) {        char c = s[right];        right++;        // 進行視窗內資料的一系列更新        if (need.count(c)) {            window[c]++;            if (window[c] == need[c])                 valid++;        }        // 判斷左側視窗是否要收縮        while (right - left >= t.size()) {            // 當視窗符合條件時，把起始索引加入 res            if (valid == need.size())                res.push_back(left);            char d = s[left];            left++;            // 進行視窗內資料的一系列更新            if (need.count(d)) {                if (window[d] == need[d])                    valid--;                window[d]--;            }        }    }    return res;}

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

四、最長無重複子串

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

這個題終於有了點新意，不是一套框架就出答案，不過反而更簡單了，稍微改一改框架就行了：

int lengthOfLongestSubstring(string s) {    unordered_map<char, int> window;    int left = 0, right = 0;    int res = 0; // 記錄結果    while (right < s.size()) {        char c = s[right];        right++;        // 進行視窗內資料的一系列更新        window[c]++;        // 判斷左側視窗是否要收縮        while (window[c] > 1) {            char d = s[left];            left++;            // 進行視窗內資料的一系列更新            window[d]--;        }        // 在這裡更新答案        res = max(res, right - left);    }    return res;}

這就是變簡單了，連 need 和 valid 都不需要，而且更新視窗內資料也只需要簡單的更新計數器 window 即可。

當 window[c] 值大於 1 時，說明視窗中存在重複字元，不符合條件，就該移動 left 縮小視窗了嘛。

唯一需要注意的是，在哪裡更新結果 res 呢？我們要的是最長無重複子串，哪一個階段可以保證視窗中的字串是沒有重複的呢？

這裡和之前不一樣，要在收縮視窗完成後更新 res，因為視窗收縮的 while 條件是存在重複元素，換句話說收縮完成後一定保證視窗中沒有重複嘛。

五、最後總結

建議背誦並默寫這套框架，順便背誦一下文章開頭的那首詩。以後就再也不怕子串、子陣列問題了好吧。