算法中的移动窗帘——C++滑动窗口算法详解
1. 滑动窗口简介
滑动窗口是一种在算法中常用的技巧，主要用来处理具有连续性的子数组或子序列问题。通过滑动窗口，可以在一维数组或字符串上维护一个固定或可变长度的窗口，逐步移动窗口，避免重复计算，从而提升效率。常用于求解子数组的最大/最小值、满足条件的子数组个数等问题。
滑动窗口的两种类型
1. 固定大小的滑动窗口：窗口大小固定不变，通常适合于问题中要求找定长子数组的最大值、最小值等情况。
2. 可变大小的滑动窗口：窗口大小根据条件动态调整，通常适用于子数组和达到一定值或满足特定条件的情况。
滑动窗口的实现步骤
以可变大小的滑动窗口为例，一般步骤如下：
1. 初始化窗口的左右边界（例如 `left` 和 `right` 指针），并根据问题需求定义窗口内需要维护的变量（如窗口内的和、计数等）。
2. 移动右边界 `right`，将新元素加入窗口，并更新窗口内的变量。
3. 检查当前窗口是否满足条件。如果满足，记录答案（如更新最大/最小值），然后移动左边界 `left` 以缩小窗口，继续寻找其他符合条件的窗口。
4. 重复步骤 2 和 3，直到右边界遍历完数组。
应用场景
滑动窗口常用于以下几类问题：
- 子数组和问题（如最大、最小和）
- 子字符串问题（如最长无重复子串）
- 符合条件的区间统计
这种方法在处理需要频繁访问连续子序列的问题时具有高效性。
2. 长度最小的子数组
一、题目介绍
二、思路解析
方法一：暴力枚举
枚举 将数组中的每个元素 都当做起点，向后遍历数组寻找最短区间，最后找到将所有元素当做期待所得结果的最小值。
优化方法：滑动窗口 ：
由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗口」的思想来解决这道题。
（1）left = 0, right = 0
（2）进窗口
- 当窗口中的值小于target是，进窗口
（3）判断什么时候出窗口并更新结果
- 当窗口中的值大于等于target时，窗口中的值减去left位置的值（更新结果），出窗口（left++）
三、代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
for (int left = 0, right = 0; right < n; right++)
{
sum += nums[right];//进窗口
while (sum >= target) // 判断
{
len = min(len, right - left + 1); // 更新结果
sum -= nums[left++]; // 出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};. - 力扣（LeetCode）
3. 无重复字符的最长子串
一、题目介绍
二、思路解析
方法一：暴力枚举 + 哈希表
方法二：滑动窗口 + 哈希表：
（1）left = 0, right = 0
- 定义一个数组模拟哈希表来记录每个字符出现的次数。
（2）进窗口
- 每当字符串出现一次时，数组中对应位置大小+1，来记录字符出现的次数
（3）判断什么时候出窗口并更新结果
- hash[s[right]]大于1，那就说明此时字符s[right]与 [left到right) 之间的字符有重复。这时开始移动left（出窗口），并且hash[s[left]]-1，这样当left移动到有重复的字符并-1时，循环结束。开始更新结果。
- hash[s[right]]没有超过1，则说明没有窗口间重符字符，更新结果，继续移动窗口right++
三、代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = { 0 };
int left = 0, right = 0, n = s.size();
int ret = 0;
while (right < n)
{
hash[s[right]]++;
while (hash[s[right]] > 1)
hash[s[left++]]--;
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};. - 力扣（LeetCode）
4. 最大连续1的个数|||
一、题目介绍
二、思路解析
滑动窗口：
（1）left = 0, right = 0
- 初始化left，right，zero。
（2）进窗口
- 遍历数组，当该元素是0时，zero++（进窗口）。
（3）判断什么时候出窗口并更新结果
- 如果此时zero大于k，left开始移动（出窗口），直到窗口中的0小于k，循环结束后更新结果。
- zero不大于k，则继续进窗口，不断更新最长连续空间的最大值。
三、代码实现
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0, zero = 0;
int ret = 0, n = nums.size();
while (right < n)
{
if (nums[right] == 0) zero++; //进窗口
while (zero > k)
if(nums[left++] == 0) zero--;//出窗口
ret = max(ret, right - left + 1); //更新结果
right++;
}
return ret;
}
};. - 力扣（LeetCode）
5. 将x减小到零的最小操作
一、题目介绍
二、思路解析
滑动窗口 + 哈希表：
（1）left = 0, right = 0
- 定义一个tmp用来存储当前窗口中的数之和，len来存储最长窗口
（2）进窗口
- 当right < n 时，tmp不断的加上当前right位置的值（进窗口）
（3）判断什么时候出窗口并更新结果
- 当窗口中的值tmp大于target时，tmp减去left位置的值，left++（出窗口）。如果窗口重的值等于target则更新结果。
三、代码实现
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int left = 0, right = 0;
int sum = 0, n = nums.size();
for (int& e : nums) sum += e;
int target = sum - x;
if (target < 0) return -1;
else if (target == 0) return n;
int tmp = 0, len = -1;
while (right < n)
{
tmp += nums[right];// 入窗口
while (tmp > target) tmp -= nums[left++]; //出窗口
if (tmp == target) len = max(len, right - left + 1); //更新结果
right++;
}
if (len == -1) return -1;
else return n - len;
}
};. - 力扣（LeetCode）
6. 水果成篮
一、题目介绍
注意：0、1、2、3分别表示是一种水果,而不是拥有水果的类型。例如0表示苹果，1表示香蕉，2表示西瓜，3表示鸭梨
二、思路解析
暴力枚举 + 哈希表
枚举 将数组中的每一个元素都当做起点开始向后遍历，直到哈希表中的值大于2，比较所有枚举结果中的最大数目
滑动窗口 + 哈希表：
（1）left = 0, right = 0
- 定义一个哈希表用来记录窗口中采摘水果的中类
（2）进窗口
- 每采摘一棵树，该树代表的水果对应哈希表中的位置+1（进窗口）。
（3）判断什么时候出窗口并更新结果
- 当hash的大小大于2时，说明此时窗口中的水果的种类超过了两种，这时开始移动left（出窗口），hash[left]--，当hash[left] 等于0时，说明窗口内没有这种水果了，删除hash表中的该种水果，更新结果。
- 当hash的大小不大于2，说明此时窗口内水果的种类没有超过2，则更新结果，继续进窗口
三、代码实现
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> hash; //统计窗口内出现了几种水果
int left = 0, right = 0;
int n = fruits.size(), ret = 0;
while (right < n)
{
hash[fruits[right]]++; // 进窗口
while (hash.size() > 2) //判断
{
//出窗口
hash[fruits[left]]--;
if (hash[fruits[left]] == 0)
hash.erase(fruits[left]);
left++;
}
ret = max(ret, right - left + 1);//更新结果
right++;
}
return ret;
}
};. - 力扣（LeetCode）
7. 找到字符串中所有字母异位词
一、题目介绍
二、思路解析
暴力枚举 + 哈希表
枚举 字符串中每三个字符 和p进行比较。用hash表记录每三个字符的种类和数量，和p进行比较。
滑动窗口 + 哈希表：
（1）left = 0, right = 0
定义两个hash表，一个用来保存 s 中的子串每个字符出现的个数，另⼀个来保存 p 中每⼀个字符出现的个数。再定义一个count用来表示窗口中符合p的异位词的个数
（2）进窗口
- for循环，每循环一次进一次窗口
（3）判断什么时候出窗口并更新结果
- 刚进窗口的字符是p中的异位词，并且此时窗口中该字符的数量小于p中该字符的数量（例如如果刚进窗口中字符是a，p中也有一个a，并且窗口前两个字符都不是a。符合条件），count++，表示窗口中是p中异位词的数量多了一个。如果此时窗口中该字符的数量大于p中该字符的数量，则不符合条件（例如窗口中【a, b, a】，p中【a, b , c】）。
- 刚进窗口中的字符不是p中的异位词，hash2[in- 'a'] <= hash1[in - 'a']也不成立（例如进窗口的字符是d，那么hash2【d - 'a'】 = 1，而p中没有d，那么hash1【d - ‘a’】= 0，定义hash表示，所有元素初始化为0，出现一次+1）
- 当窗口大小大于p的大小时，移动left，此时出窗口的字符如果是p的异位词并且窗口中该字符的数量不多于p中该字符的数量（例如上面的【a, b, a】，当移走第一个a时，hash表中字符a所在位置的大小为2，就不执行count--），count--，窗口中是p的异位词的数量-1，最后hash表中left移动前所在位置-1（出窗口）。
- 当count == p的大小时，说明窗口中都是p的异位词
三、代码实现
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
//统计字符串p中每个字符的个数
int hash1[26] = { 0 };
for (auto e : p) hash1[e- 'a']++;
//统计滑动窗口中中每个字符的个数
int hash2[26] = { 0 };
int count = 0;
for (int left = 0, right = 0; right < s.size(); right++)
{
char in = s[right];
hash2[in - 'a']++;//进窗口
if (hash2[in- 'a'] <= hash1[in - 'a']) count++;//维护count
if (right - left + 1 > p.size())
{
char out = s[left++];
if (hash2[out - 'a'] <= hash1[out - 'a']) count--;//维护count
hash2[out - 'a']--;//出窗口
}
//更新结果
if (count == p.size()) ret.push_back(left);
}
return ret;
}
};. - 力扣（LeetCode）
8. 串联所有单词的子串
一、题目介绍
二、思路解析
非就是之前处理的对象是⼀个⼀个的字符，我们这里处理的对象是⼀个⼀个的单词。小伙伴们可以照着上题的思路自己想一想做一做，做题思路这里不再赘述。
三、代码实现
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
//跑存words中所有字符串的个数
unordered_map<string, int> hash1;
for (auto& st: words) hash1[st]++;
int n = words[0].size(), m = words.size();
for (int i = 0; i < n; i++)
{
unordered_map<string, int> hash2;
for(int left = i, right = i, count = 0; right + n <= s.size(); right += n)
{
string in = s.substr(right, n);
hash2[in]++;// 入窗口
if (hash1[in] && hash2[in] <= hash1[in]) count++;// 维护count
//判断
if (right - left + 1 > n * m)
{
string out = s.substr(left, n);
if (hash1[out] && hash2[out] <= hash1[out]) count--;// 维护count
hash2[out]--;//出窗口
left += n;
}
if (count == m) ret.push_back(left);
}
}
return ret;
}
};9. 最小覆盖子串
一、题目介绍
二、思路解析
暴力枚举 + 哈希表
枚举 从中的每个字符开始向后遍历数组，直到找到覆盖t的位置，比较枚举的所有结果选取最小值。
滑动窗口 + 哈希表：
（1）left = 0, right = 0
定义两个hash表⼀个将目标串的信息统计起来，另⼀个哈希表动态的维护窗口内字符串的信息。定义一个kind，统计目标传中字符的种类。定义count统计窗口中能够覆盖t的字符种类的数量。
（2）进窗口
for循环，进窗口
（3）判断什么时候出窗口和更新结果
- 只有当窗口中的某一字符数等于t中的该字符的个数时，count才会+1（例如t中有两个A，那么只有窗口中出现第二个A时，才会执行count++，第一个A出现时不会执行count++）。
- 当count == kind时，说明此时窗口可以覆盖字符串t，更新结果，记录下此时窗口的起始位置和窗口的长度。然后判断是否count--，移动left，hash[left]--（出窗口）。
三、代码实现
class Solution {
public:
string minWindow(string s, string t) {
string ret;
int hash1[128] = { 0 };// 统计t中每个字符出现的次数
int kinds = 0; // 统计t中字符的种类
for (auto& e : t)
if ( hash1[e]++ == 0 ) kinds++;
int hash2[128] = { 0 }; // 统计s中每个字符出现的次数
int n = s.size(), m = t.size();
int minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < n; right++)
{
char in = s[right];
hash2[in]++; // 入窗口
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
hash2[out]--;//出窗口
}
}
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};. - 力扣（LeetCode）