滑動窗口算法技巧

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

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

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 縮小窗口
        window.remove(s[left]);
        left++;
    }
}

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

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

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

/* 滑動窗口算法框架 */
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ù)的地方，到時候你直接往里面填就行了 。

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

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

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

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

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

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

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

可以使用方括號訪問鍵對應(yīng)的值map[key]。需要注意的是，如果該key不存在，C++ 會自動創(chuàng)建這個 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ī)Т蠹铱纯此降子卸? 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 的所有字母:
            更新答案

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

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

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

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

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

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

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

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

初始狀態(tài)：

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

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

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

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

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

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

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()) {
    // 開始滑動
}

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

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

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

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

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

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

如果一個字符進(jìn)入窗口，應(yīng)該增加window計數(shù)器；如果一個字符將移出窗口的時候，應(yīng)該減少window計數(shù)器；當(dāng)valid滿足need時應(yīng)該收縮窗口；應(yīng)該在收縮窗口的時候更新最終結(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)某個字符在window的數(shù)量滿足了need的需要，就要更新valid，表示有一個字符已經(jīng)滿足要求。而且，你能發(fā)現(xiàn)，兩次對窗口內(nèi)數(shù)據(jù)的更新操作是完全對稱的。

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

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

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

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

二、字符串排列

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

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

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

首先，先復(fù)制粘貼之前的算法框架代碼，然后明確剛才提出的 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++;
        // 進(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;
}

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

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

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

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

三、找所有字母異位詞

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

呵呵，這個所謂的字母異位詞，不就是排列嗎，搞個高端的說法就能糊弄人了嗎？ 相當(dāng)于，輸入一個串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; // 記錄結(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)窗口符合條件時，把起始索引加入 res
            if (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;
}

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

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

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

這個題終于有了點(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ù)也只需要簡單的更新計數(shù)器window即可。

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

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

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

五、最后總結(jié)

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

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