?申明： 未經(jīng)許可，禁止以任何形式轉(zhuǎn)載，若要引用，請(qǐng)標(biāo)注鏈接地址。 全文共計(jì)6244字，閱讀大概需要3分鐘
??更多學(xué)習(xí)內(nèi)容， 歡迎??關(guān)注??文末我的個(gè)人微信公眾號(hào)：不懂開(kāi)發(fā)的程序猿
個(gè)人網(wǎng)站：https://jerry-jy.co/

滑動(dòng)窗口算法

思路

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

理論上你可以設(shè)計(jì)兩端都開(kāi)或者兩端都閉的區(qū)間，但設(shè)計(jì)為左閉右開(kāi)區(qū)間是最方便處理的。因?yàn)檫@樣初始化 left = right = 0 時(shí)區(qū)間 [0, 0) 中沒(méi)有元素，但只要讓 right 向右移動(dòng)（擴(kuò)大）一位，區(qū)間 [0, 1) 就包含一個(gè)元素 0 了。如果你設(shè)置為兩端都開(kāi)的區(qū)間，那么讓 right 向右移動(dòng)一位后開(kāi)區(qū)間 (0, 1) 仍然沒(méi)有元素；如果你設(shè)置為兩端都閉的區(qū)間，那么初始區(qū)間 [0, 0] 就包含了一個(gè)元素。這兩種情況都會(huì)給邊界處理帶來(lái)不必要的麻煩。

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)解

框架

/* 滑動(dòng)窗口算法框架 */
void slidingWindow(string s) {
    // 用合適的數(shù)據(jù)結(jié)構(gòu)記錄窗口中的數(shù)據(jù)
    unordered_map<char, int> window, need;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是將移入窗口的字符
        char c = s[right];
        // 增大窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        ...

        /*** debug 輸出的位置 ***/
        // 注意在最終的解法代碼中不要 print
        // 因?yàn)?IO 操作很耗時(shí)，可能導(dǎo)致超時(shí)
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判斷左側(cè)窗口是否要收縮
        while (window needs shrink) {
            // d 是將移出窗口的字符
            char d = s[left];
            // 縮小窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            ...
        }
    }
}

Java 處理字符串不方便，所以代碼為 C++ 實(shí)現(xiàn)。

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

可以使用方括號(hào)訪(fǎng)問(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)。

另外，Java 中的 Integer 和 String 這種包裝類(lèi)不能直接用 == 進(jìn)行相等判斷，而應(yīng)該使用類(lèi)的 equals 方法。

需要思考以下幾個(gè)問(wèn)題：

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

2、什么時(shí)候窗口應(yīng)該暫停擴(kuò)大，開(kāi)始移動(dòng) left 縮小窗口？從窗口移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)？

3、我們要的結(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 滿(mǎn)足 need 時(shí)應(yīng)該收縮窗口；應(yīng)該在收縮窗口的時(shí)候更新最終結(jié)果。

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

76. 最小覆蓋子串[hard]

給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

/**
 * 求字符串 s 中包含字符串 t 所有字符的最小子串
 * @param s 源字符串
 * @param t 給定字符串
 * @return 滿(mǎn)足條件的最小子串
 */
class Solution {
    public String minWindow(String s, String t) {
    // 用于記錄需要的字符和窗口中的字符及其出現(xiàn)的次數(shù)
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    // 統(tǒng)計(jì) t 中各字符出現(xiàn)次數(shù)
    for (char c : t.toCharArray()) 
        need.put(c, need.getOrDefault(c, 0) + 1);

    int left = 0, right = 0;
    int valid = 0; // 窗口中滿(mǎn)足需要的字符個(gè)數(shù)
    // 記錄最小覆蓋子串的起始索引及長(zhǎng)度
    int start = 0, len = Integer.MAX_VALUE;
    while (right < s.length()) {
        // c 是將移入窗口的字符
        char c = s.charAt(right);
        // 擴(kuò)大窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c)))
                valid++; // 只有當(dāng) window[c] 和 need[c] 對(duì)應(yīng)的出現(xiàn)次數(shù)一致時(shí)，才能滿(mǎn)足條件，valid 才能 +1
        }

        // 判斷左側(cè)窗口是否要收縮
        while (valid == need.size()) {
            // 更新最小覆蓋子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是將移出窗口的字符
            char d = s.charAt(left);
            // 縮小窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--; // 只有當(dāng) window[d] 內(nèi)的出現(xiàn)次數(shù)和 need[d] 相等時(shí)，才能 -1
                window.put(d, window.get(d) - 1);
            }
        }
    }
    // 返回最小覆蓋子串
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

使用 Java 的讀者要尤其警惕語(yǔ)言特性的陷阱。Java 的 Integer，String 等類(lèi)型判定相等應(yīng)該用 equals 方法而不能直接用等號(hào) ==，這是 Java 包裝類(lèi)的一個(gè)隱晦細(xì)節(jié)。所以在縮小窗口更新數(shù)據(jù)的時(shí)候，不能直接改寫(xiě)為 window.get(d) == need.get(d)，而要用 window.get(d).equals(need.get(d))，之后的題目代碼同理。

567. 字符串的排列

給你兩個(gè)字符串 s1 和 s2 ，寫(xiě)一個(gè)函數(shù)來(lái)判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。

換句話(huà)說(shuō)，s1 的排列之一是 s2 的 子串 。

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

class Solution {
    public boolean checkInclusion(String s1, String s2) {
    // 用于記錄需要的字符和窗口中的字符及其出現(xiàn)的次數(shù)
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    // 統(tǒng)計(jì) s1 中各字符出現(xiàn)次數(shù)
    for(int i = 0; i < s1.length(); i++){
        char c = s1.charAt(i);
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0; // 窗口中滿(mǎn)足需要的字符個(gè)數(shù)
    // 記錄最小覆蓋子串的起始索引及長(zhǎng)度
    //int start = 0, len = Integer.MAX_VALUE;
    while (right < s2.length()) {
        // c 是將移入窗口的字符
        char c = s2.charAt(right);
        // 擴(kuò)大窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c)))
                valid++; // 只有當(dāng) window[c] 和 need[c] 對(duì)應(yīng)的出現(xiàn)次數(shù)一致時(shí)，才能滿(mǎn)足條件，valid 才能 +1
        }

        // 判斷左側(cè)窗口是否要收縮
        while (right - left >= s1.length()) {
            // 在這里判斷是否找到了合法的子串，窗口中有一個(gè)合法的排列，就立即返回
            if (valid == need.size()) {
                return true;
            }
            // d 是將移出窗口的字符
            char d = s2.charAt(left);
            // 縮小窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--; // 只有當(dāng) window[d] 內(nèi)的出現(xiàn)次數(shù)和 need[d] 相等時(shí)，才能 -1
                window.put(d, window.get(d) - 1);
            }
        }
    }
    // 未找到符合條件的子串
    return false;
    }
}

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

總結(jié)：對(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ò)大和縮小，和最小覆蓋子串完全相同。

由于這道題中 [left, right) 其實(shí)維護(hù)的是一個(gè)定長(zhǎng)的窗口，窗口大小為 t.size()。因?yàn)槎ㄩL(zhǎng)窗口每次向前滑動(dòng)時(shí)只會(huì)移出一個(gè)字符，所以可以把內(nèi)層的 while 改成 if，效果是一樣的。

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

給定兩個(gè)字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。

異位詞 指由相同字母重排列形成的字符串（包括相同的字符串）。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
    // 用于記錄需要的字符和窗口中的字符及其出現(xiàn)的次數(shù)
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    // 統(tǒng)計(jì) p 中各字符出現(xiàn)次數(shù)
    for(int i = 0; i < p.length(); i++){
        char c = p.charAt(i);
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0; // 窗口中滿(mǎn)足需要的字符個(gè)數(shù)
    // 記錄保存符合條件索引位置
    List<Integer> res = new ArrayList<>();
    while (right < s.length()) {
        // c 是將移入窗口的字符
        char c = s.charAt(right);
        // 擴(kuò)大窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c)))
                valid++; // 只有當(dāng) window[c] 和 need[c] 對(duì)應(yīng)的出現(xiàn)次數(shù)一致時(shí)，才能滿(mǎn)足條件，valid 才能 +1
        }

        // 判斷左側(cè)窗口是否要收縮
        while (right - left >= p.length()) {
            // 在這里判斷是否找到了合法的子串，窗口中有一個(gè)合法的排列，就立即將索引加入list中
            if (valid == need.size()) {
                res.add(left);
            }
            // d 是將移出窗口的字符
            char d = s.charAt(left);
            // 縮小窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--; // 只有當(dāng) window[d] 內(nèi)的出現(xiàn)次數(shù)和 need[d] 相等時(shí)，才能 -1
                window.put(d, window.get(d) - 1);
            }
        }
    }
    // 未找到符合條件的子串
    return res;        
    }
}

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

3. 無(wú)重復(fù)字符的最長(zhǎng)子串

給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();

    int left = 0, right = 0;
    // 記錄結(jié)果
    int res = 0;
    while (right < s.length()) {
        // c 是將移入窗口的字符
        char c = s.charAt(right);
        // 擴(kuò)大窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 判斷左側(cè)窗口是否要收縮
        while (window.get(c) > 1) {
            // d 是將移出窗口的字符
            char d = s.charAt(left);
            // 縮小窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            window.put(d, window.get(d) - 1);
        }
        // 在這里更新答案
        res = Math.max(res, right - left);
    }
    // 未找到符合條件的子串
    return res;         
    }        
}

–end–文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-408143.html

到了這里，關(guān)于LeetCode算法小抄--滑動(dòng)窗口算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！