【优选算法篇】踏入算法的深邃乐章：滑动窗口的极致探秘

C++ 滑动窗口详解：进阶题解与思维分析

💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。 👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！ 🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习滑动窗口的基础与进阶！

前言

接上篇【优选算法篇】编织算法的流动诗篇：滑动窗口的轻盈之美

在算法的世界中，滑动窗口是一种极具优雅和灵活性的算法技巧。在上一章中，我们通过几个经典问题初步领略了滑动窗口的强大之处。然而，算法的探索并没有止步于此。随着问题的复杂性逐渐提升，滑动窗口的应用场景也变得更加丰富多样。在这篇博客中，我们将继续深入探讨滑动窗口的进阶应用。通过更加灵活的策略、动态调整窗口，我们将解决一系列复杂的算法挑战，进一步揭示滑动窗口的无限可能。

接下来，让我们步入滑动窗口的进阶领域，探索更多算法之美。

第二章：进阶挑战

2.1 水果成篮

题目链接：904. 水果成篮

题目描述： 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果，但是有一些规则：

• 你有两个篮子，每个篮子只能装一种类型的水果，篮子的容量无限制。
• 你可以选择任意一棵树开始采摘，但必须从这棵树开始依次向右采摘每棵树上的水果。
• 一旦遇到某棵树上的水果不符合篮子中的水果种类，你必须停止采摘。

返回你能采摘的最多的水果数量。

示例 1：

• 输入：fruits = [1,2,1]
• 输出：3
• 解释：你可以采摘所有 3 棵树上的水果。

示例 2：

• 输入：fruits = [0,1,2,2]
• 输出：3
• 解释：你只能采摘 [1,2,2] 这三棵树的水果。如果从第 1 棵树开始采摘，只能采摘到 [0,1]。

示例 3：

• 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
• 输出：5
• 解释：你可以采摘 [1,2,1,1,2] 这五棵树的水果。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

解法一：滑动窗口

算法思路：

本题是典型的滑动窗口问题。要求我们找到一个连续区间，其中只能有两种不同种类的水果（即至多两个不同元素）。通过滑动窗口，我们可以动态调整区间大小，保持窗口内水果种类不超过两种。

具体步骤：

1. 用一个哈希表 hash 记录滑动窗口内的水果种类和数量。
2. 滑动窗口的右边界 right 向右移动，每次将新水果加入哈希表。
3. 如果哈希表中记录的水果种类超过两个，左边界 left 开始向右移动，直到窗口内水果种类不超过两个为止。
4. 在每次满足条件时，更新最大收集到的水果数量 ret。

算法流程：

1. 初始化哈希表 hash，左右指针 left 和 right，以及记录结果的变量 ret。
2. 遍历数组 fruits，对每个水果进行如下操作：
   • 将 right 指向的水果加入哈希表，统计频次。
   • 如果哈希表的大小超过 2，左指针 left 向右移动，同时更新哈希表，直到哈希表中只有两种水果。
   • 在满足条件时，更新最大采摘数量 ret。
3. 返回结果。

代码实现：

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash; // 统计滑动窗口内水果的种类和数量
        int ret = 0; // 记录最大水果数量
        int left = 0; // 左指针
        
        for (int right = 0; right < fruits.size(); ++right) {
            hash[fruits[right]]++; // 右指针扩展窗口，加入新水果
            
            // 如果种类超过 2，收缩窗口
            while (hash.size() > 2) {
                hash[fruits[left]]--; // 移除左边水果
                if (hash[fruits[left]] == 0) {
                    hash.erase(fruits[left]); // 种类为 0，删除该水果
                }
                left++; // 左指针向右移动
            }
            
            ret = max(ret, right - left + 1); // 更新最大水果数量
        }
        
        return ret;
    }
};

解法二：滑动窗口 + 数组模拟哈希表

算法思路：

利用数组 hash 来代替哈希表，用水果种类的值直接作为数组下标，来统计每种水果的数量。这种方式效率更高，因为直接使用数组的下标访问比哈希表操作更快。

代码实现：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0};  // 数组模拟哈希表
        int ret = 0;             // 记录结果
        int left = 0;            // 左指针
        int kinds = 0;           // 记录当前窗口内的水果种类数
        
        for (int right = 0; right < fruits.size(); ++right) {
            if (hash[fruits[right]] == 0) kinds++;  // 新种类水果进入窗口
            hash[fruits[right]]++;  // 统计数量
            
            // 当水果种类超过 2 时，收缩窗口
            while (kinds > 2) {
                hash[fruits[left]]--;  // 移除左边水果
                if (hash[fruits[left]] == 0) kinds--;  // 种类数量减少
                left++;  // 左指针右移
            }
            
            ret = max(ret, right - left + 1);  // 更新最大水果数量
        }
        
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n)，每个元素最多被左右指针访问两次。
• 空间复杂度：O(n)，哈希表或数组最多存储 n 种水果的频次。

图解分析：

示例：

• 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
• 输出：5
• 解释：你可以采摘 [1,2,1,1,2] 这五棵树的水果。

滑动窗口执行过程图解：

详细说明：

1. Iteration 1-3：Right 扩展到 2，窗口内只有一种水果 3，因此子数组为 [3,3,3]，长度为 3。
2. Iteration 4：加入水果 1，种类增加到两种，窗口变为 [3,3,3,1]，长度更新为 4。
3. Iteration 5：加入水果 2，种类增加到三种，此时需要调整窗口，移动 Left，直到只剩两种水果。经过调整，窗口变为 [1,2,1]。
4. Iteration 6-8：继续右移 Right，窗口内的水果种类保持为两种，最大长度更新为 5，子数组为 [1,2,1,1,2]。
5. Iteration 9-11：加入水果 3，水果种类再次超出限制，继续收缩窗口，最终找到的最大子数组长度为 5。

2.2 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

题目描述：

给定两个字符串 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^4
• s 和 p 仅包含小写字母。

解法：滑动窗口 + 哈希表

算法思路：

这道题要求我们在字符串 s 中找到所有与字符串 p 的 异位词 对应的子串。由于异位词由相同字母组成且长度与 p 相同，因此我们可以使用滑动窗口来解决这一问题。

1. 窗口大小固定： 因为异位词的长度一定与字符串 p 的长度相同，所以我们构造一个长度为 p.size() 的滑动窗口，每次右移窗口，动态维护窗口内每个字母的出现频次。
2. 频次匹配判断： 通过两个大小为 26 的数组来统计字母出现的次数，分别用于存储当前窗口内字母频次（hash2）和 p 中的字母频次（hash1）。当两个数组的内容相同，说明当前窗口就是 p 的一个异位词。
3. 窗口移动： 每次右移窗口时，更新窗口内字母的频次。如果窗口超过 p.size()，需要将最左边的字母移出窗口。若在滑动过程中，两个数组的内容始终保持一致，那么我们记录该窗口的起始索引。

算法流程：

1. 初始化两个大小为 26 的数组 hash1 和 hash2，分别记录 p 中字母的频次和窗口中字母的频次。
2. 遍历字符串 s，使用右指针 right 逐渐扩大窗口：
   • 每次将窗口右端的字母加入窗口，并更新其频次。
   • 若窗口超过 p.size()，则需要从左侧移出一个字母，并更新频次。
3. 当 hash1 和 hash2 相等时，说明当前窗口是 p 的一个异位词，记录其起始位置。 因为直接比较两个哈希表时间复杂度很高，这里我们想到了一种优化方式，要判断窗口字符串是否是异位词，我们只需要判断同一种字符在两个字符串中出现的次数是否一样即可，这里我们使用count来统计有效字符的个数即可轻松判断窗口字符串是否是p的异位词
4. 最后返回所有满足条件的起始位置列表。

代码实现：

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
        for(auto ch : p) hash1[ch - 'a']++; 
        
        int hash2[26] = { 0 }; // 统计窗口里面的每一个字符出现的个数
        int m = p.size();
        
        for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            // 进窗口 + 维护 count
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            
            if(right - left + 1 > m) {  // 判断窗口是否需要收缩
                char out = s[left++];
                // 出窗口 + 维护 count
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            
            // 更新结果
            if(count == m) ret.push_back(left);
        }
        
        return ret;
    }
};

这里面count是指有效字符的个数，很巧妙的判断滑动窗口里的字符串是否满足条件

复杂度分析：

• 时间复杂度：O(n)，每个字符最多被左右指针访问两次，因此时间复杂度为线性。
• 空间复杂度：O(1)，只需要常数级别的额外空间用于存储两个固定大小的数组。

图解分析：

假设输入为 s = "cbaebabacd", p = "abc"，通过滑动窗口的执行过程如下：

滑动窗口执行过程图解：

详细说明：

1. Iteration 1-3：Right=0 到 Right=2，窗口内包含 [c, b, a]，它与 p="abc" 完全匹配，属于异位词，记录起始索引 0。
2. Iteration 4：Right=3，窗口内包含 [b, a, e]，字母 e 不在 p 中，因此当前窗口不是异位词。
3. Iteration 5：Right=4，窗口内包含 [a, e, b]，依旧不匹配 p，当前窗口不是异位词。
4. Iteration 6：Right=5，窗口内包含 [e, b, a]，仍然不匹配 p，当前窗口不是异位词。
5. Iteration 7：Right=6，窗口内包含 [b, a, d]，d 不在 p 中，因此当前窗口不是异位词。
6. Iteration 8：Right=7，窗口内包含 [a, b, a]，当前窗口不是异位词。
7. Iteration 9：Right=8，窗口内包含 [b, a, c]，这再次是 p="abc" 的排列，属于异位词，记录起始索引 6。
8. Iteration 10：Right=9，窗口内包含 [a, c, d]，d 不在 p 中，因此当前窗口不是异位词。

2.3 串联所有单词的子串

题目链接：30. 串联所有单词的子串

题目描述：

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。s 中的 串联子串 是指包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串，而 "acdbef" 不是串联子串，因为它不是 words 排列的连接。

返回所有串联子串在 s 中的开始索引，顺序可以不考虑。

示例 1：

• 输入：s = "barfoothefoobarman", words = ["foo","bar"]
• 输出：[0,9]
• 解释： 子串 "barfoo" 的起始索引为 0，它是 words 中按顺序排列的连接。 子串 "foobar" 的起始索引为 9，它是 words 中按顺序排列的连接。

示例 2：

• 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
• 输出：[]
• 解释： 字符串中没有符合要求的串联子串。

示例 3：

• 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
• 输出：[6,9,12]
• 解释： 子串 "foobarthe" 的起始索引为 6，它是 words 中按顺序排列的连接。 子串 "barthefoo" 的起始索引为 9，子串 "thefoobar" 的起始索引为 12。

提示：

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 仅包含小写英文字母。

解法：滑动窗口+哈希表

算法思路：

本题可以类比为寻找字符串中所有字母异位词的变种问题。不同的是，这里处理的对象是单词而不是单个字符。我们需要遍历字符串 s，并通过滑动窗口找到所有符合条件的单词排列。

在这里插入图片描述

具体步骤：

1. 使用哈希表 hash1 记录 words 中每个单词的频次。
2. 遍历字符串 s，每次滑动窗口的大小为 words 中单词的总长度。
3. 在每个窗口内，维护另一个哈希表 hash2，用于记录当前窗口内单词的频次。
4. 当两个哈希表的内容一致时，说明当前窗口是一个符合要求的串联子串，记录其起始索引。 同理，这里比较两个哈希表是否相等时间复杂度也很高，所以我们还是采用优化方式，使用count变量来统计有效字符串的个数即可

算法流程：

1. 初始化 hash1，用于存储 words 中单词的频次。
2. 遍历 s，通过滑动窗口按单词长度为步长，维护窗口内单词的频次。
3. 当窗口内的单词频次与 words 中的单词频次一致时，记录该窗口的起始索引。

代码实现：

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;  // 保存 words 中所有单词的频次
        for (auto& word : words) hash1[word]++;
        
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) {  // 执行 len 次
            unordered_map<string, int> hash2;  // 维护窗口内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) {
                string in = s.substr(right, len);  // 进窗口
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
                
                // 判断是否需要缩小窗口
                if (right - left + 1 > len * m) {
                    string out = s.substr(left, len);  // 出窗口
                    if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }
                
                // 更新结果
                if (count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n * m * l)，其中 n 是字符串 s 的长度，m 是 words 中单词的个数，l 是单词的长度。每个单词被扫描一次，并且最多执行 len 次完整的窗口扫描。
• 空间复杂度：O(m * l)，用于存储 words 中单词的哈希表以及滑动窗口中的哈希表。

图解分析：

滑动窗口执行过程图解：

假设输入为 s = "barfoothefoobarman", words = ["foo", "bar"]，通过滑动窗口的执行过程如下：

具体过程和上一道题类似，核心没变，操作对象从单个字符变成字符串而已，以及一些细节的处理，其他都没啥了，这里就不详细分析了

详细说明：

1. Iteration 1：窗口内的单词为 [bar]，不构成完整的串联子串。
2. Iteration 2：窗口扩大，内含 [bar, foo]，它是 words 中单词的排列，记录起始索引 0。
3. Iteration 3：窗口滑动，内含 [foo, bar]，它是 words 中单词的排列，记录起始索引 9。

2.4 最小覆盖子串

题目链接：76. 最小覆盖子串

题目描述：

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

注意：

• 对于 t 中重复的字符，最小子串中该字符数量必须不少于 t 中的字符数量。
• 如果存在这样的子串，答案是唯一的。

示例 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 中只有一个 ‘a’，因此不存在符合条件的子串。

提示：

• 1 <= s.length, t.length <= 10^4
• s 和 t 由英文字母组成。

解法：滑动窗口 + 哈希表

算法思路：

这是一个典型的滑动窗口问题。目标是找到字符串 s 中能够覆盖 t 所有字符的最小子串。解决思路如下：

1. 滑动窗口的应用：
   • 我们使用两个哈希表，一个用来记录 t 中每个字符的频次，另一个用来动态维护滑动窗口中的字符频次。
   • 当窗口内的字符满足 t 中每个字符的频次要求时，窗口就是一个可行的解。
2. 动态调整窗口大小：
   • 通过不断扩大窗口右边界，将字符加入窗口。
   • 一旦窗口内的字符满足 t 的要求，开始缩小窗口左边界，尽量缩短窗口长度。

算法流程：

1. 初始化两个哈希表，hash1 用来记录 t 中每个字符的频次，hash2 用来记录窗口内的字符频次。
2. 使用滑动窗口，右指针 right 不断向右扩展窗口，同时更新窗口内的字符频次。
3. 每当窗口内的字符频次满足 t 中的要求，开始收缩左指针 left，缩小窗口并更新最小子串的长度。
4. 当遍历结束后，返回最小子串的起始索引和长度。

这里面还是需要判断两个哈希表是否相等，我们这里还是采用的优化方式，使用count变量来统计有效字符，不过之前两道题是为了统计字符出现的频次，这道题我们统计的是字符出现的种类，所以count的++和--的情况有所变化喔

代码实现：

#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 }; // 记录字符串 t 中每个字符的频次
        int kinds = 0;          // 统计 t 中不同的字符种类
        for (auto ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }

        int hash2[128] = { 0 }; // 记录窗口中每个字符的频次
        int minlen = INT_MAX, begin = -1; // 初始化最小长度和起始位置
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++;  // 进窗口 + 维护 count
            
            // 如果当前窗口满足条件，尝试收缩窗口
            while (count == kinds) {
                if (right - left + 1 < minlen) {    // 更新最小长度和起始位置
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];               // 收缩窗口
                if (hash2[out]-- == hash1[out]) count--;  // 出窗口 + 维护 count
            }
        }

        // 返回结果
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，滑动窗口遍历每个字符最多两次。
• 空间复杂度：O(1)，哈希表的大小固定为 128，存储字符频次。

图解分析：

假设输入为 s = "ADOBECODEBANC", t = "ABC"，滑动窗口的执行过程如下：

滑动窗口执行过程图解：

详细说明：

1. Iteration 1-5：滑动窗口从 Left=0 开始向右扩展，但字符尚未覆盖 t="ABC" 的所有字符，因此没有有效窗口。
2. Iteration 6：Right=5 时，窗口内字符为 [A, D, O, B, E, C]，此时首次找到覆盖 t 的有效窗口，记录最小子串为 "ADOBEC"。
3. Iteration 7-10：随着窗口向右扩展，字符无法继续满足 t 的要求，最小子串保持为 "ADOBEC"。
4. Iteration 11：Right=10 时，窗口内字符为 [D, O, B, E, C, O, D, E, B, A]，再次满足条件，最小子串仍保持为 "ADOBEC"。
5. Iteration 12：窗口左移到 Left=5，依然保持有效窗口，字符为 [C, O, D, E, B, A]，最小子串保持不变。
6. Iteration 16：Right=12 时，窗口内字符为 [B, A, N, C]，再次找到有效窗口，更新最小子串为 "BANC"。

写在最后

在这篇博客中，我们继续探索了滑动窗口的高级应用，通过对一系列复杂问题的深度剖析，进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束，还是「找到字符串中所有字母异位词」的字符频次比较，抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题，这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用，结合不同场景的需求，展现了它在复杂算法挑战中的无限可能性。我们不仅解决了实际问题，更深入理解了滑动窗口的算法思想和设计精髓，为后续的算法学习打下了坚实基础。

以上就是关于【优选算法篇】踏入算法的深邃乐章：滑动窗口的极致探秘的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️