我写了首诗，把滑动窗口算法变成了默写题

labuladong约 12567 字大约 42 分钟滑动窗口核心框架数组

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
3. Longest Substring Without Repeating Charactersopen in new window	3. 无重复字符的最长子串open in new window	🟠
438. Find All Anagrams in a Stringopen in new window	438. 找到字符串中所有字母异位词open in new window	🟠
567. Permutation in Stringopen in new window	567. 字符串的排列open in new window	🟠
76. Minimum Window Substringopen in new window	76. 最小覆盖子串open in new window	🔴
-	剑指 Offer 48. 最长不含重复字符的子字符串open in new window	🟠
-	剑指 Offer II 014. 字符串中的变位词open in new window	🟠
-	剑指 Offer II 015. 字符串中的所有变位词open in new window	🟠
-	剑指 Offer II 016. 不含重复字符的最长子字符串open in new window	🟠
-	剑指 Offer II 017. 含有所有字符的最短字符串open in new window	🔴

Tip

本文有视频版：滑动窗口算法核心模板框架open in new window。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

鉴于前文二分搜索框架详解的那首《二分搜索升天词》很受好评，并在民间广为流传，成为安睡助眠的一剂良方，今天在滑动窗口算法框架中，我再次编写一首小诗来歌颂滑动窗口算法的伟大（手动狗头）：

哈哈，我自己快把自己夸上天了，大家乐一乐就好，不要当真：）

关于双指针的快慢指针和左右指针的用法，可以参见前文双指针技巧汇总，本文就解决一类最难掌握的双指针技巧：滑动窗口技巧。总结出一套框架，可以保你闭着眼睛都能写出正确的解法。

说起滑动窗口算法，很多读者都会头疼。这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案么。LeetCode 上有起码 10 道运用滑动窗口算法的题目，难度都是中等和困难。该算法的大致逻辑如下：

int left = 0, right = 0;

while (left < right && right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

这个算法技巧的时间复杂度是 O(N)，比字符串暴力算法要高效得多。

其实困扰大家的，不是算法的思路，而是各种细节问题。比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。即便你明白了这些细节，也容易出 bug，找 bug 还不知道怎么找，真的挺让人心烦的。

所以今天我就写一套滑动窗口算法的代码框架，我连再哪里做输出 debug 都给你写好了，以后遇到相关的问题，你就默写出来如下框架然后改三个地方就行，还不会出 bug：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

/* 滑动窗口算法框架 */
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据
    HashMap<Character, Integer> window = new HashMap<>();

    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        System.out.printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            window.put(d, window.get(d) - 1);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据
    unordered_map<char, int> window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c)
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d)
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

def slidingWindow(s: str):
    # 用合适的数据结构记录窗口中的数据
    window = {}
    
    left = 0
    right = 0
    
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        if c not in window:
            window[c] = 1
        else:
            window[c] += 1
            
        # 增大窗口
        right += 1
        
        # 进行窗口内数据的一系列更新
        # ...
        
        # 判断左侧窗口是否要收缩
        while left < right and window needs shrink:
            # d 是将移出窗口的字符
            d = s[left]
            
            # 缩小窗口
            left += 1
            
            # 进行窗口内数据的一系列更新
            # ...

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

// 滑动窗口算法框架
func slidingWindow(s string) {
    // 用合适的数据结构记录窗口中的数据
    window := make(map[byte]int)

    left, right := 0, 0
    for right < len(s) {
        // c 是将移入窗口的字符
        c := s[right]
        window[c]++
        // 增大窗口
        right++
        // 进行窗口内数据的一系列更新

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要输出
        // 因为 IO 操作很耗时，可能导致超时
        fmt.Printf("window: [%d, %d)\n", left, right)
        /********************/

        // 判断左侧窗口是否要收缩
        for left < right && window needs shrink {
            // d 是将移出窗口的字符
            d := s[left]
            window[d]--
            // 缩小窗口
            left++
            // 进行窗口内数据的一系列更新
        }
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

var slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据
    const window = new Map();
    
    let left = 0, right = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        window.set(c, (window.get(c) || 0) + 1);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 console.log
        // 因为 IO 操作很耗时，可能导致超时
        console.log("window: [" + left + ", " + right + ")");
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            let d = s[left];
            window.set(d, window.get(d) - 1);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

其中两处 ... 表示的更新窗口数据的地方，到时候你直接往里面填就行了。

而且，这两个 ... 处的操作分别是扩大和缩小窗口的更新操作，等会你会发现它们操作是完全对称的。

另外，虽然滑动窗口代码框架中有一个嵌套的 while 循环，但算法的时间复杂度依然是 O(N)，其中 N 是输入字符串/数组的长度。

为什么呢？简单说，指针 left, right 不会回退（它们的值只增不减），所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。后文算法时空复杂度分析实用指南有具体讲时间复杂度的估算，这里就不展开了。

说句题外话，我发现很多人喜欢执着于表象，不喜欢探求问题的本质。比如说有很多人评论我这个框架，说什么散列表速度慢，不如用数组代替散列表；还有很多人喜欢把代码写得特别短小，说我这样代码太多余，影响编译速度，LeetCode 上速度不够快。

我的意见是，算法主要看时间复杂度，你能确保自己的时间复杂度最优就行了。至于 LeetCode 所谓的运行速度，那个都是玄学，只要不是慢的离谱就没啥问题，根本不值得你从编译层面优化，不要舍本逐末……

我的公众号重点在于算法思想，你把框架思维了然于心，然后随你魔改代码好吧，你高兴就好。

言归正传，下面就直接上四道力扣原题来套这个框架，其中第一道题会详细说明其原理，后面四道就直接闭眼睛秒杀了。

因为滑动窗口很多时候都是在处理字符串相关的问题，而 Java 处理字符串不方便，所以本文代码为 C++ 实现。不会用到什么特定的编程语言技巧，但是还是简单介绍一下一些用到的数据结构，以免有的读者因为语言的细节问题阻碍对算法思想的理解：

unordered_map 就是哈希表（字典），相当于 Java 的 HashMap，它的一个方法 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)。

另外，Java 中的 Integer 和 String 这种包装类不能直接用 == 进行相等判断，而应该使用类的 equals 方法，这个语言特性坑了不少读者，在代码部分我会给出具体提示。

一、最小覆盖子串

先来看看力扣第 76 题「最小覆盖子串open in new window」难度 Hard：

76. 最小覆盖子串 | 力扣 | LeetCode |

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

^{m == s.length}
^{n == t.length}
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

就是说要在 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) 称为一个「窗口」。

Tip

理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。

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、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

下面是完整代码：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

/**
 * 求字符串 s 中包含字符串 t 所有字符的最小子串
 * @param s 源字符串
 * @param t 给定字符串
 * @return 满足条件的最小子串
 */
public String minWindow(String s, String t) {
    // 用于记录需要的字符和窗口中的字符及其出现的次数
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    // 统计 t 中各字符出现次数
    for (char c : t.toCharArray()) 
        need.put(c, need.getOrDefault(c, 0) + 1);

    int left = 0, right = 0;
    int valid = 0; // 窗口中满足需要的字符个数
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = Integer.MAX_VALUE;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c)))
                valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1
                window.put(d, window.get(d) - 1);
            }
        }
    }

    // 返回最小覆盖子串
    return len == Integer.MAX_VALUE ?
        "" : s.substring(start, start + len);
}

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

    int left = 0, right = 0;/**<extend down -200><div class="img-content"><img src="/algo/images/slidingwindow/1.png" class="myimage"/></div> */
    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()) {/**<extend down -200><div class="img-content"><img src="/algo/images/slidingwindow/2.png" class="myimage"/></div> */
            // 在这里更新最小覆盖子串
            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]--;
            }                    
        }/**<extend up -50><div class="img-content"><img src="/algo/images/slidingwindow/4.png" class="myimage"/></div> */
    }
    // 返回最小覆盖子串
    return len == INT_MAX ?
        "" : s.substr(start, len);
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

def minWindow(s: str, t: str) -> str:
    from collections import defaultdict

    need, window = defaultdict(int), defaultdict(int)
    for c in t:
        need[c] += 1

    left, right = 0, 0
    valid = 0
    # 记录最小覆盖子串的起始索引及长度
    start, length = 0, float('inf')
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        # 扩大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

        # 判断左侧窗口是否要收缩
        while valid == len(need):
            # 在这里更新最小覆盖子串
            if right - left < length:
                start = left
                length = right - left

            # d 是将移出窗口的字符
            d = s[left]
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    # 返回最小覆盖子串
    return "" if length == float('inf') else s[start:start + length]

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

func minWindow(s string, t string) string {
    need := make(map[byte]int) // 用于统计需要凑齐的字符
    window := make(map[byte]int) // 记录滑动窗口内已有字符的个数
    for i := range t {
        need[t[i]]++
    }
    left, right := 0, 0 // 滑动窗口的左右边界
    valid := 0 // 判断窗口中是否已经包含了字串 t 中所有字符
    start, length := 0, math.MaxInt32 // 最小覆盖子串的起始索引及长度
    for right < len(s) { // 当 right 小于 s 的长度时，继续循环
        c := s[right] // c 是将要加入窗口中的字符
        right++
        if _, ok := need[c]; ok { // 如果这个字符在字串 t 中需要的话
            window[c]++ // 加入窗口中
            if window[c] == need[c] { // 如果字符 c 在窗口中的数量已经满足其在字串 t 中的数量
                valid++ // 计数器 valid 加一
            }
        }
        for valid == len(need) { // 如果滑动窗口中的字符已经完全覆盖字串 t 中的字符
            if right-left < length { // 如果此时的覆盖子串更短
                start = left // 更新最小覆盖子串的起始索引
                length = right - left // 更新最小子串的长度
            }
            d := s[left] // d 是将要移出窗口的字符
            left++ // 左侧窗口右移
            if _, ok := need[d]; ok { // 如果这个字符在字串 t 中需要的话
                if window[d] == need[d] { // 如果这个字符已经满足了他在字串 t 中的需求
                    valid-- // 计数器 valid 减一
                }
                window[d]-- // 移出窗口
            }
        }
    }
    if length == math.MaxInt32 { // 如果最小子串长度没有更新，则返回空格
        return ""
    }
    return s[start : start+length] // 返回最小覆盖子串
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    // 哈希表 need 记录需要匹配的字符及对应的出现次数
    // 哈希表 window 记录窗口中满足 need 条件的字符及其出现次数
    let need = new Map();
    let window = new Map();
    for (let i = 0; i < t.length; i++) {
        if (need.has(t[i])) {
            need.set(t[i], need.get(t[i]) + 1);
        } else {
            need.set(t[i], 1);
        }
    }
    let left = 0, right = 0;
    let valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    let start = 0, len = Infinity;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            if (window.has(c)) {
                window.set(c, window.get(c) + 1);
            } else {
                window.set(c, 1);
            }
            if (window.get(c) === need.get(c)) {
                valid++;
            }
        }
        // 判断左侧窗口是否要收缩
        while (valid === need.size) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            let d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                window.set(d, window.get(d) - 1);
            }
        }
    }
    // 返回最小覆盖子串
    return len === Infinity ? '' : s.substr(start, len);
};

Warning

使用 Java 的读者要尤其警惕语言特性的陷阱。Java 的 Integer，String 等类型判定相等应该用 equals 方法而不能直接用等号 ==，这是 Java 包装类的一个隐晦细节。所以在缩小窗口更新数据的时候，不能直接改写为 window.get(d) == need.get(d)，而要用 window.get(d).equals(need.get(d))，之后的题目代码同理。

需要注意的是，当我们发现某个字符在 window 的数量满足了 need 的需要，就要更新 valid，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。

当 valid == need.size() 时，说明 T 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。

移动 left 收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

至此，应该可以完全理解这套框架了，滑动窗口算法又不难，就是细节问题让人烦得很。以后遇到滑动窗口算法，你就按照这框架写代码，保准没有 bug，还省事儿。

下面就直接利用这套框架秒杀几道题吧，你基本上一眼就能看出思路了。

二、字符串排列

这是力扣第 567 题「字符串的排列open in new window」，难度中等：

567. 字符串的排列 | 力扣 | LeetCode |

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

注意哦，输入的 s1 是可以包含重复字符的，所以这个题难度不小。

这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

首先，先复制粘贴之前的算法框架代码，然后明确刚才提出的几个问题，即可写出这道题的答案：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

public boolean checkInclusion(String t, String s) {
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c)))
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.length()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--;
                window.put(d, window.getOrDefault(d, 0) - 1);
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

// 判断 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;
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

# 判断 s 中是否存在 t 的排列
def checkInclusion(t: str, s: str) -> bool:
    from collections import defaultdict
    need, window = defaultdict(int), defaultdict(int)
    for c in t:
        need[c] += 1

    left, right = 0, 0
    valid = 0
    while right < len(s):
        c = s[right]
        right += 1
        # 进行窗口内数据的一系列更新
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

        # 判断左侧窗口是否要收缩
        while right - left >= len(t):
            # 在这里判断是否找到了合法的子串
            if valid == len(need):
                return True
            d = s[left]
            left += 1
            # 进行窗口内数据的一系列更新
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    # 未找到符合条件的子串
    return False

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

// 判断 s 中是否存在 t 的排列
func checkInclusion(t string, s string) bool {
    need := make(map[byte]int)
    window := make(map[byte]int)
    for _, c := range []byte(t) {
        need[c]++
    }
    left := 0
    right := 0
    valid := 0
    for right < len(s) {
        c := s[right]
        right++
        // 进行窗口内数据的一系列更新
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        // 判断左侧窗口是否要收缩
        for right-left >= len(t) {
            // 在这里判断是否找到了合法的子串
            if valid == len(need) {
                return true
            }
            d := s[left]
            left++
            // 进行窗口内数据的一系列更新
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
    // 未找到符合条件的子串
    return false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

var checkInclusion = function(t, s) {
    let need = new Map();
    let window = new Map();
    for (let c of t) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    let left = 0, right = 0;
    let valid = 0;
    while (right < s.length) {
        let c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) == need.get(c))
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.length) {
            // 在这里判断是否找到了合法的子串
            if (valid === need.size)
                return true;
            let d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) == need.get(d))
                    valid--;
                window.set(d, window.get(d) - 1);
            }
        }
    }
    // 未找到符合条件的子串
    return false;
};

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变几个地方：

1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列嘛，显然长度应该是一样的。

2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

Note

由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。

三、找所有字母异位词

这是力扣第 438 题「找到字符串中所有字母异位词open in new window」，难度中等：

438. 找到字符串中所有字母异位词 | 力扣 | LeetCode |

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

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

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10⁴
s 和 p 仅包含小写字母

呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

直接默写一下框架，明确刚才讲的 4 个问题，即可秒杀这道题：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

public List<Integer> findAnagrams(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, right = 0;
    int valid = 0;
    List<Integer> res = new ArrayList<>(); // 记录结果
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        // 进行窗口内数据的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.length()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size()) {
                res.add(left);
            }
            char d = s.charAt(left);
            left++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return res;
}

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;
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

from typing import List
from collections import defaultdict

def findAnagrams(s: str, t: str) -> List[int]:
    need, window = defaultdict(int), defaultdict(int)
    for c in t:
        need[c] += 1

    left, right = 0, 0
    valid = 0
    res = []
    while right < len(s):
        c = s[right]
        right += 1
        # 进行窗口内数据的一系列更新
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1
        # 判断左侧窗口是否要收缩
        while right - left >= len(t):
            # 当窗口符合条件时，把起始索引加入 res
            if valid == len(need):
                res.append(left)
            d = s[left]
            left += 1
            # 进行窗口内数据的一系列更新
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return res

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

func findAnagrams(s string, t string) []int {
    need := make(map[rune]int) // 记录目标字符串 t 中每个字符的出现次数
    window := make(map[rune]int) // 记录窗口中每个字符出现的次数
    for _, c := range t { // 初始化 need
        need[c]++
    }

    left, right := 0, 0
    valid := 0
    res := []int{} // 记录结果
    for right < len(s) {
        c := rune(s[right])
        right++

        if _, ok := need[c]; ok { // 开始滑动窗口，进行窗口数据更新
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        for right-left >= len(t) { // 判断左侧窗口是否要收缩
            if valid == len(need) { // 如果当前窗口符合条件，把窗口左侧索引加入 res
                res = append(res, left)
            }
            d := rune(s[left])
            left++

            if _, ok := need[d]; ok { // 进行窗口内数据的更新
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

/**
 * @param {string} s
 * @param {string} t
 * @return {number[]}
 */
var findAnagrams = function(s, t) {
    // 定义 need，window 计数 Map
    var need = new Map();
    var window = new Map();
    // 统计 t 中出现的元素以及它们的个数
    for (var i = 0; i < t.length; i++) {
        var c = t[i];
        if (need.has(c)) {
            need.set(c, need.get(c) + 1);
        } else {
            need.set(c, 1);
        }
    }

    var left = 0, right = 0;
    var valid = 0;
    var res = []; // 记录结果
    while (right < s.length) {
        var c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            if (window.has(c)) {
                window.set(c, window.get(c) + 1);
            } else {
                window.set(c, 1);
            }
            if (need.get(c) === window.get(c)) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.length) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid === need.size) {
                res.push(left);
            }
            var d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) === need.get(d))
                    valid--;
                window.set(d, window.get(d) - 1);
            }
        }
    }
    return res;
};

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。

四、最长无重复子串

这是力扣第 3 题「无重复字符的最长子串open in new window」，难度中等：

3. 无重复字符的最长子串 | 力扣 | LeetCode |

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10⁴
s 由英文字母、数字、符号和空格组成

这个题终于有了点新意，不是一套框架就出答案，不过反而更简单了，稍微改一改框架就行了：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

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

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        // 进行窗口内数据的一系列更新
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 判断左侧窗口是否要收缩
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            left++;
            // 进行窗口内数据的一系列更新
            window.put(d, window.get(d) - 1);
        }
        // 在这里更新答案
        res = Math.max(res, right - left);
    }
    return res;
}

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;
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

def lengthOfLongestSubstring(s: str) -> int:
    window = {}  # 用于记录窗口中各字符出现的次数
    left, right = 0, 0  # 窗口的左右边界
    res = 0  # 用于记录结果

    while right < len(s):
        c = s[right]
        right += 1
        window[c] = window.get(c, 0) + 1  # 更新窗口和字符的出现次数

        # 判断窗口是否需要收缩
        while window[c] > 1:
            d = s[left]
            left += 1
            window[d] -= 1  # 更新窗口和字符的出现次数

        res = max(res, right - left)  # 更新结果

    return res

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

func lengthOfLongestSubstring(s string) int {
    window := make(map[byte]int)

    left, right := 0, 0
    res := 0 // 记录结果
    for right < len(s) {
        c := s[right]
        right++
        // 进行窗口内数据的一系列更新
        window[c]++
        // 判断左侧窗口是否要收缩
        for window[c] > 1 {
            d := s[left]
            left++
            // 进行窗口内数据的一系列更新
            window[d]--
        }
        // 在这里更新答案
        res = max(res, right - left)
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。

var lengthOfLongestSubstring = function(s) {
    var window = {};
    var left = 0, right = 0;
    var res = 0;
    while (right < s.length) {
        var c = s[right];
        right++;
        if (window[c] !== undefined) { // window中已经有了c
            window[c]++;
        } else {
            window[c] = 1;
        }
        while (window[c] > 1) {
            var d = s[left];
            left++;
            window[d]--;
        }
        res = Math.max(res, right - left);
    }
    return res;
};

这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。

唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

好了，滑动窗口算法模板就讲到这里，希望大家能理解其中的思想，记住算法模板并融会贯通。回顾一下，遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：

1、什么时候应该扩大窗口？

2、什么时候应该缩小窗口？

3、什么时候应该更新答案？

我在滑动窗口经典习题open in new window 中使用这套思维模式列举了更多经典的习题，旨在强化你对算法的理解和记忆，以后就再也不怕子串、子数组问题了。

引用本文的文章

【强化练习】单调队列的通用实现及经典习题【强化练习】滑动窗口算法经典习题分治算法详解：运算优先级动态规划设计：最大子数组单调队列结构解决滑动窗口问题双指针技巧秒杀七道数组题目归并排序详解及应用我的刷题心得数据结构精品课本站简介滑动窗口算法延伸：Rabin Karp 字符匹配算法算法时空复杂度分析实用指南

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
1004. Max Consecutive Ones IIIopen in new window	1004. 最大连续1的个数 IIIopen in new window
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limitopen in new window	1438. 绝对差不超过限制的最长连续子数组open in new window
1658. Minimum Operations to Reduce X to Zeroopen in new window	1658. 将 x 减到 0 的最小操作数open in new window
209. Minimum Size Subarray Sumopen in new window	209. 长度最小的子数组open in new window
219. Contains Duplicate IIopen in new window	219. 存在重复元素 IIopen in new window
220. Contains Duplicate IIIopen in new window	220. 存在重复元素 IIIopen in new window
395. Longest Substring with At Least K Repeating Charactersopen in new window	395. 至少有 K 个重复字符的最长子串open in new window
424. Longest Repeating Character Replacementopen in new window	424. 替换后的最长重复字符open in new window
713. Subarray Product Less Than Kopen in new window	713. 乘积小于 K 的子数组open in new window
862. Shortest Subarray with Sum at Least Kopen in new window	862. 和至少为 K 的最短子数组open in new window
-	剑指 Offer 48. 最长不含重复字符的子字符串open in new window
-	剑指 Offer 57 - II. 和为s的连续正数序列open in new window
-	剑指 Offer II 008. 和大于等于 target 的最短子数组open in new window
-	剑指 Offer II 009. 乘积小于 K 的子数组open in new window
-	剑指 Offer II 014. 字符串中的变位词open in new window
-	剑指 Offer II 015. 字符串中的所有变位词open in new window
-	剑指 Offer II 016. 不含重复字符的最长子字符串open in new window
-	剑指 Offer II 017. 含有所有字符的最短字符串open in new window
-	剑指 Offer II 057. 值和下标之差都在给定的范围内open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 一、最小覆盖子串

# 二、字符串排列

# 三、找所有字母异位词

# 四、最长无重复子串

一、最小覆盖子串

二、字符串排列

三、找所有字母异位词

四、最长无重复子串