C++ 滑动窗口算法进阶解析与实战
本文深入讲解 C++ 滑动窗口算法,涵盖水果成篮、寻找字母异位词、串联所有单词的子串及最小覆盖子串四个经典题目。通过哈希表优化与双指针技巧,详细分析了时间复杂度 O(n) 的实现方案,提供代码示例与图解,帮助读者掌握滑动窗口在复杂场景下的应用。

本文深入讲解 C++ 滑动窗口算法,涵盖水果成篮、寻找字母异位词、串联所有单词的子串及最小覆盖子串四个经典题目。通过哈希表优化与双指针技巧,详细分析了时间复杂度 O(n) 的实现方案,提供代码示例与图解,帮助读者掌握滑动窗口在复杂场景下的应用。


微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
在算法的世界中,滑动窗口是一种极具优雅和灵活性的算法技巧。通过更加灵活的策略、动态调整窗口,我们将解决一系列复杂的算法挑战,进一步揭示滑动窗口的无限可能。
题目链接:904. 水果成篮
题目描述:
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果,但是有一些规则:
返回你能采摘的最多的水果数量。
示例 1:
fruits = [1,2,1]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 种水果的频次。Right 扩展到 2,窗口内只有一种水果 3,因此子数组为 [3,3,3],长度为 3。1,种类增加到两种,窗口变为 [3,3,3,1],长度更新为 4。2,种类增加到三种,此时需要调整窗口,移动 Left,直到只剩两种水果。经过调整,窗口变为 [1,2,1]。Right,窗口内的水果种类保持为两种,最大长度更新为 5,子数组为 [1,2,1,1,2]。3,水果种类再次超出限制,继续收缩窗口,最终找到的最大子数组长度为 5。题目链接: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() 的滑动窗口,每次右移窗口,动态维护窗口内每个字母的出现频次。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),只需要常数级别的额外空间用于存储两个固定大小的数组。Right=0 到 Right=2,窗口内包含 [c, b, a],它与 p="abc" 完全匹配,属于异位词,记录起始索引 0。Right=3,窗口内包含 [b, a, e],字母 e 不在 p 中,因此当前窗口不是异位词。Right=8,窗口内包含 [b, a, c],这再次是 p="abc" 的排列,属于异位词,记录起始索引 6。题目链接: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.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 是单词的长度。O(m * l),用于存储 words 中单词的哈希表以及滑动窗口中的哈希表。题目链接: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++]; // 收缩窗口
if (hash2[out]-- == hash1[out]) count--; // 出窗口 + 维护 count
}
}
// 返回结果
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};
O(n),其中 n 是字符串 s 的长度,滑动窗口遍历每个字符最多两次。O(1),哈希表的大小固定为 128,存储字符频次。本文深入探讨了滑动窗口的高级应用,通过对一系列复杂问题的深度剖析,进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束,还是「找到字符串中所有字母异位词」的字符频次比较,抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题,这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用,结合不同场景的需求,展现了它在复杂算法挑战中的无限可能性。