文章目录
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 <= 1050 <= fruits[i] < fruits.length
解法一：滑动窗口
算法思路：
具体步骤：
- 用一个哈希表
hash记录滑动窗口内的水果种类和数量。 - 滑动窗口的右边界
right向右移动，每次将新水果加入哈希表。 - 如果哈希表中记录的水果种类超过两个，左边界
left开始向右移动，直到窗口内水果种类不超过两个为止。 - 在每次满足条件时，更新最大收集到的水果数量
ret。
算法流程：
- 初始化哈希表
hash，左右指针left和right，以及记录结果的变量ret。 - 遍历数组
fruits，对每个水果进行如下操作：- 将
right指向的水果加入哈希表，统计频次。 - 如果哈希表的大小超过 2，左指针
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;
}
};
解法二：滑动窗口 + 数组模拟哈希表
算法思路：
代码实现：
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]这五棵树的水果。
滑动窗口执行过程图解：
详细说明：
- 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"的异位词。
示例 2：
- 输入：
s = "abab",p = "ab" - 输出：
[0,1,2] - 解释：
起始索引为0的子串是"ab"，它是"ab"的异位词。
起始索引为1的子串是"ba"，它是"ab"的异位词。
起始索引为2的子串是"ab"，它是"ab"的异位词。
提示：
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母。
解法：滑动窗口 + 哈希表
算法思路：
-
窗口大小固定：
因为异位词的长度一定与字符串p的长度相同，所以我们构造一个长度为p.size()的滑动窗口，每次右移窗口，动态维护窗口内每个字母的出现频次。 -
频次匹配判断：
通过两个大小为 26 的数组来统计字母出现的次数，分别用于存储当前窗口内字母频次（hash2）和p中的字母频次（hash1）。当两个数组的内容相同，说明当前窗口就是p的一个异位词。 -
窗口移动：
每次右移窗口时，更新窗口内字母的频次。如果窗口超过p.size()，需要将最左边的字母移出窗口。若在滑动过程中，两个数组的内容始终保持一致，那么我们记录该窗口的起始索引。
算法流程：
- 初始化两个大小为 26 的数组
hash1和hash2，分别记录p中字母的频次和窗口中字母的频次。 - 遍历字符串
s，使用右指针right逐渐扩大窗口：- 每次将窗口右端的字母加入窗口，并更新其频次。
- 若窗口超过
p.size()，则需要从左侧移出一个字母，并更新频次。
- 当
hash1和hash2相等时，说明当前窗口是p的一个异位词，记录其起始位置。
- 最后返回所有满足条件的起始位置列表。
代码实现：
#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)，只需要常数级别的额外空间用于存储两个固定大小的数组。
图解分析：
假设输入为 s = "cbaebabacd", p = "abc"，通过滑动窗口的执行过程如下：
滑动窗口执行过程图解：
详细说明：
-
Iteration 1-3：
Right=0到Right=2，窗口内包含[c, b, a]，它与p="abc"完全匹配，属于异位词，记录起始索引0。 -
Iteration 4：
Right=3，窗口内包含[b, a, e]，字母e不在p中，因此当前窗口不是异位词。 -
Iteration 5：
Right=4，窗口内包含[a, e, b]，依旧不匹配p，当前窗口不是异位词。 -
Iteration 6：
Right=5，窗口内包含[e, b, a]，仍然不匹配p，当前窗口不是异位词。 -
Iteration 7：
Right=6，窗口内包含[b, a, d]，d不在p中，因此当前窗口不是异位词。 -
Iteration 8：
Right=7，窗口内包含[a, b, a]，当前窗口不是异位词。 -
Iteration 9：
Right=8，窗口内包含[b, a, c]，这再次是p="abc"的排列，属于异位词，记录起始索引6。 -
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^41 <= words.length <= 50001 <= words[i].length <= 30words[i]和s仅包含小写英文字母。
解法：滑动窗口+哈希表
算法思路：
具体步骤：
- 使用哈希表
hash1记录words中每个单词的频次。 - 遍历字符串
s，每次滑动窗口的大小为words中单词的总长度。 - 在每个窗口内，维护另一个哈希表
hash2，用于记录当前窗口内单词的频次。 - 当两个哈希表的内容一致时，说明当前窗口是一个符合要求的串联子串，记录其起始索引。
算法流程：
- 初始化
hash1，用于存储words中单词的频次。 - 遍历
s，通过滑动窗口按单词长度为步长，维护窗口内单词的频次。 - 当窗口内的单词频次与
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"]，通过滑动窗口的执行过程如下：
详细说明：
- Iteration 1：窗口内的单词为
[bar]，不构成完整的串联子串。 - Iteration 2：窗口扩大，内含
[bar, foo]，它是words中单词的排列，记录起始索引0。 - 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^4s和t由英文字母组成。
解法：滑动窗口 + 哈希表
算法思路：
算法流程：
- 初始化两个哈希表，
hash1用来记录t中每个字符的频次，hash2用来记录窗口内的字符频次。 - 使用滑动窗口，右指针
right不断向右扩展窗口，同时更新窗口内的字符频次。 - 每当窗口内的字符频次满足
t中的要求，开始收缩左指针left，缩小窗口并更新最小子串的长度。 - 当遍历结束后，返回最小子串的起始索引和长度。
代码实现：
#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"，滑动窗口的执行过程如下：
滑动窗口执行过程图解：
详细说明：
- Iteration 1-5：滑动窗口从
Left=0开始向右扩展，但字符尚未覆盖t="ABC"的所有字符，因此没有有效窗口。 - Iteration 6：
Right=5时，窗口内字符为[A, D, O, B, E, C]，此时首次找到覆盖t的有效窗口，记录最小子串为"ADOBEC"。 - Iteration 7-10：随着窗口向右扩展，字符无法继续满足
t的要求，最小子串保持为"ADOBEC"。 - Iteration 11：
Right=10时，窗口内字符为[D, O, B, E, C, O, D, E, B, A]，再次满足条件，最小子串仍保持为"ADOBEC"。 - Iteration 12：窗口左移到
Left=5，依然保持有效窗口，字符为[C, O, D, E, B, A]，最小子串保持不变。 - Iteration 16：
Right=12时，窗口内字符为[B, A, N, C]，再次找到有效窗口，更新最小子串为"BANC"。
写在最后
以上就是关于【优选算法篇】踏入算法的深邃乐章：滑动窗口的极致探秘的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️