C++算法
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，存储字符频次。本文深入探讨了滑动窗口的高级应用，通过对一系列复杂问题的深度剖析，进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束，还是「找到字符串中所有字母异位词」的字符频次比较，抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题，这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用，结合不同场景的需求，展现了它在复杂算法挑战中的无限可能性。