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]。
提示：
1 <= fruits.length <= 10^50 <= fruits[i] < fruits.length
解法一：滑动窗口
算法思路： 本题是典型的滑动窗口问题。要求我们找到一个连续区间，其中只能有两种不同种类的水果（即至多两个不同元素）。通过滑动窗口，我们可以动态调整区间大小，保持窗口内水果种类不超过两种。
具体步骤：
- 用一个哈希表
hash记录滑动窗口内的水果种类和数量。 - 滑动窗口的右边界
right向右移动，每次将新水果加入哈希表。 - 如果哈希表中记录的水果种类超过两个，左边界
left开始向右移动，直到窗口内水果种类不超过两个为止。 - 在每次满足条件时，更新最大收集到的水果数量
ret。
代码实现：
#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种水果的频次。
详细说明：
- Iteration 1-3：
Right扩展到2，窗口内只有一种水果3，因此子数组为[3,3,3]，长度为3。 - Iteration 4：加入水果
1，种类增加到两种，窗口变为[3,3,3,1]，长度更新为4。 - Iteration 5：加入水果
2，种类增加到三种，此时需要调整窗口，移动Left，直到只剩两种水果。经过调整，窗口变为[1,2,1]。 - Iteration 6-8：继续右移
Right，窗口内的水果种类保持为两种，最大长度更新为5，子数组为[1,2,1,1,2]。 - 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"的异位词。
提示：
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母。
解法：滑动窗口 + 哈希表
算法思路：
这道题要求我们在字符串 s 中找到所有与字符串 p 的 异位词 对应的子串。由于异位词由相同字母组成且长度与 p 相同，因此我们可以使用滑动窗口来解决这一问题。
- 窗口大小固定：因为异位词的长度一定与字符串
p的长度相同，所以我们构造一个长度为p.size()的滑动窗口，每次右移窗口，动态维护窗口内每个字母的出现频次。 - 频次匹配判断：通过两个大小为 26 的数组来统计字母出现的次数，分别用于存储当前窗口内字母频次（
hash2）和p中的字母频次（hash1）。当两个数组的内容相同，说明当前窗口就是p的一个异位词。 - 优化判断：要判断窗口字符串是否是异位词，只需要判断同一种字符在两个字符串中出现的次数是否一样即可，这里使用
count来统计有效字符的个数即可轻松判断。
代码实现：
#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;
}
};
复杂度分析：
- 时间复杂度：
O(n)，每个字符最多被左右指针访问两次，因此时间复杂度为线性。 - 空间复杂度：
O(1)，只需要常数级别的额外空间用于存储两个固定大小的数组。
详细说明：
- Iteration 1-3：
Right=0到Right=2，窗口内包含[c, b, a]，它与p="abc"完全匹配，属于异位词，记录起始索引0。 - Iteration 4：
Right=3，窗口内包含[b, a, e]，字母e不在p中，因此当前窗口不是异位词。 - Iteration 9：
Right=8，窗口内包含[b, a, c]，这再次是p="abc"的排列，属于异位词，记录起始索引6。
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中按顺序排列的连接。
提示：
1 <= s.length <= 10^41 <= words.length <= 50001 <= words[i].length <= 30words[i]和s仅包含小写英文字母。
解法：滑动窗口+哈希表
算法思路：
本题可以类比为寻找字符串中所有字母异位词的变种问题。不同的是，这里处理的对象是单词而不是单个字符。我们需要遍历字符串 s，并通过滑动窗口找到所有符合条件的单词排列。
- 使用哈希表
hash1记录words中每个单词的频次。 - 遍历字符串
s，每次滑动窗口的大小为words中单词的总长度。 - 在每个窗口内，维护另一个哈希表
hash2，用于记录当前窗口内单词的频次。 - 当两个哈希表的内容一致时，说明当前窗口是一个符合要求的串联子串，记录其起始索引。同样采用
count变量来统计有效字符串的个数进行优化。
代码实现：
#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.(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
(count == m) ret.(left);
}
}
ret;
}
};
复杂度分析：
- 时间复杂度：
O(n * m * l)，其中n是字符串s的长度，m是words中单词的个数，l是单词的长度。 - 空间复杂度：
O(m * l)，用于存储words中单词的哈希表以及滑动窗口中的哈希表。
2.4 最小覆盖子串
题目链接：76. 最小覆盖子串
题目描述：
给你一个字符串 s 和一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。
注意：
- 对于
t中重复的字符，最小子串中该字符数量必须不少于t中的字符数量。 - 如果存在这样的子串，答案是唯一的。
示例 1：
- 输入：
s = "ADOBECODEBANC",t = "ABC" - 输出：
"BANC" - 解释：最小覆盖子串
"BANC"包含字符串t的 'A'、'B' 和 'C'。
提示：
1 <= s.length, t.length <= 10^4s和t由英文字母组成。
解法：滑动窗口 + 哈希表
算法思路：
这是一个典型的滑动窗口问题。目标是找到字符串 s 中能够覆盖 t 所有字符的最小子串。解决思路如下：
- 滑动窗口的应用：使用两个哈希表，一个用来记录
t中每个字符的频次，另一个用来动态维护滑动窗口中的字符频次。 - 动态调整窗口大小：通过不断扩大窗口右边界，将字符加入窗口。一旦窗口内的字符满足
t的要求，开始缩小窗口左边界，尽量缩短窗口长度。 - 优化判断：使用
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++]; // 收缩窗口
(hash2[out]-- == hash1[out]) count--;
}
}
(begin == ) ;
s.(begin, minlen);
}
};
复杂度分析：
- 时间复杂度：
O(n)，其中n是字符串s的长度，滑动窗口遍历每个字符最多两次。 - 空间复杂度：
O(1)，哈希表的大小固定为 128，存储字符频次。
总结
本文深入探讨了滑动窗口的高级应用，通过对一系列复杂问题的深度剖析，进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束，还是「找到字符串中所有字母异位词」的字符频次比较，抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题，这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用，结合不同场景的需求，展现了它在复杂算法挑战中的无限可能性。
