前言
前面我们已经把双指针的一些习题练习的差不多啦
今天我们来学习新的算法知识——滑动窗口
让我们一起来探索滑动窗口的魅力吧
滑动窗口
滑动窗口算法（Sliding Window Algorithm）是一种用于处理数组、字符串等线性数据结构的高效算法。它通过维护一个动态的窗口来优化计算过程。滑动窗口的核心思想是通过逐步移动窗口来获得所需的结果，而不是每次都从头开始重新计算。这个方法能够减少时间复杂度，从而提高算法效率。
滑动窗口算法的基本思想
滑动窗口算法分为两个主要类型：
1.固定大小窗口（Fixed-size Sliding Window）：窗口的大小在整个过程中保持不变。
2.可变大小窗口（Variable-size Sliding Window）：窗口的大小可以根据需求变化，通常是通过扩展或收缩窗口来满足特定条件。
滑动窗口的工作原理
1.初始化窗口：在数据结构的开始处创建一个窗口，并根据问题的需要选择适当的大小。
2.移动窗口：窗口通常从左到右（或其他方向）滑动，每次滑动时，更新窗口内的信息。
3.计算或更新结果：每次移动窗口时，计算窗口内的相关信息，通常是某种聚合值（如求和、最大值等）。
滑动窗口的应用场景
滑动窗口算法常用于以下几种常见问题中：
1.最大子数组和问题：给定一个整数数组，找到其所有连续子数组的和的最大值。
2.无重复字符的最长子串：给定一个字符串，找到其中没有重复字符的最长子串的长度。
3.最小覆盖子串：给定一个字符串和一个字符集合，找到覆盖所有字符的最小子串。
4.固定大小子数组的滑动：找到所有固定大小的子数组中，和最大的子数组。
实践是检验真理的唯一标准，一起来刷题吧
长度最小的子数组
思路
首先想到的肯定是暴力解法：
「从前往后」枚举数组中的任意一个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找一段最短的区间，使得这段区间的和「大于等于」目标值。将所有元素作为起始位置所得的结果中，找到「最小值」即可。
不用多说，超时是必然的。
这题分析的对象时一段连续的区间，由此我们想到可以试试滑动窗口来解决
让滑动窗口满足：从 i 位置开始，窗口内所有元素的和小于 target （那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度）
每一次将右端元素划入窗口，然后统计出窗口内元素和
如果窗口内元素和小于 target，那就 right++，继续将右边元素划入窗口
如果窗口内元素和大于等于target，那就更新结果，并且将左端元素划去窗口，同时判断是否满足条件并更新结果，直到小于target
话不多说上代码吧
class Solution
{
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int n = nums.size(), ans = INT_MAX;
int sum = 0;
for(int left = 0, right = 0; right < n; right++)
{
sum += nums[right]; // 右端元素划入窗口
while(sum >= target)
{
ans = min(ans, right - left + 1); // 满足条件更新结果
sum -= nums[left];
left++;
}
}
return ans == INT_MAX ? 0 : ans;
}
};
无重复字符的最长子串
思路
第一种还是暴力解法，试了一试，发现能过
思路就是每到一个位置，就遍历到无重复子串能到什么位置，找出最大长度就行
怎么判断已经到了有重复字母的位置能，我们可以用哈希表来计数，统计频次，频次大于1就截止
代码如下：
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int ret = 0; // 记录结果
int n = s.length();
// 1. 枚举从不同位置开始的最长重复子串
// 枚举起始位置
for (int i = 0; i < n; i++)
{
// 创建一个哈希表，统计频次
int hash[128] = { 0 };
// 寻找结束为止
for (int j = i; j < n; j++)
{
hash[s[j]]++; // 统计字符出现的频次
if (hash[s[j]] > 1) // 如果出现重复的
break;
// 如果没有重复，就更新 ret
ret = max(ret, j - i + 1);
}
}
// 2. 返回结果
return ret;
}
};
第二种解法就是滑动窗口了
想到这里是一段连续的区间，我们可以使用滑动窗口来优化
让窗口满足所有元素都不相同，右端字符不断进入窗口，然后用哈希统计频次，一旦频次有大于 1 的 就从左边划出窗口，直到这个字符频次等于1，再更新结果
如果没有大于1的频次的字符，就一直更新结果就好啦
代码如下：
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int hash[128] = {0}; // 使用数组模拟哈希
int right = 0, left = 0, n = s.size();
int ans = 0;
while(right < n)
{
hash[s[right]]++; // 进窗口
while(hash[s[right]] > 1) // 维护窗口
{
hash[s[left++]]--;
}
ans = max(ans, right - left + 1);// 更新结果
right++; // 下一个元素进窗口
}
return ans;
}
};
最大连续1的个数
思路
粗看不知道怎么处理，细看想想有个k
那不就是一段连续的 1 区间塞进去 k 个 0，我们可以把问题转化成：
求一段最长的连续区间，要求这段区间内的 0 的个数不超过 k 个，连续区间问题就来到了我们的滑动窗口
流程：
right一直向右遍历，如果等于0 就进窗口，k–，每次判断 k是否小于0，如果小于 0 就处理左边left，直到 k 大于等于 0 ，同时更新结果
代码如下：
class Solution
{
public:
int longestOnes(vector<int>& nums, int k)
{
int n = nums.size(), ans = 0;
for(int left = 0, right = 0; right < n; right++)
{
if(nums[right] == 0) // 进窗口
{
k--;
}
while(k < 0) // 判断，维护窗口
{
if(nums[left] == 0)
{
k++;
}
left ++ ;
}
ans = max(ans, right - left + 1); // 更新结果
}
return ans ;
}
};
将x减到0的最小操作数
思路
题目要求的是 左右 两端 连续的和为x的最短数组，处理起来相对比较麻烦，我们不如反过来看，数组和为sum，sum - x就是剩下中间连续数组的和，那我们就可以把原来的问题转化成：
一段和为sum - x的最长连续子数组，又来到我们的滑动窗口啦
转化问题：求 target = sum(nums) - x 。如果 target < 0 ，问题无解
b. 初始化左右指针 l = 0 , r = 0 （滑动窗口区间表示为 [l, r) ，左右区间是否开闭很重要，必须设定与代码一致），记录当前滑动窗口内数组和的变量 sum = 0 ，记录当前满足条件数组的最大区间长度 maxLen = -1
c. 当r 小于等于数组长度时，一直循环
i. 如果 sum < target ，右移右指针，直至变量和大于等于 target ，或右指针已经移到头；
ii. 如果 sum > target ，右移左指针，直至变量和小于等于 target ，或左指针已经移到头；
iii. 如果经过前两步的左右移动使得 sum == target ，维护满足条件数组的最大长度，并让下个元素进入窗口
d. 循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回-1
代码如下：
class Solution
{
public:
int minOperations(vector<int>& nums, int x)
{
int sum = 0;
for(int a : nums) sum += a;
int target = sum - x;
// 细节问题
if(target < 0) return -1; // 这里就代表整个数组都小于 x
int ret = -1;
for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
{
tmp += nums[right]; // 进窗口
while(tmp > target) // 维护窗口
tmp -= nums[left++];
if(tmp == target)
ret = max(ret, right - left + 1);// 更新结果
}
if(ret == -1) return ret;
else return nums.size() - ret;
}
};
总结
通过四个有关滑动窗口的题目，让我深有体会
主要就是抓住了核心——一段连续的区间
然后对连续的区间进行维护以及处理，滑动窗口在处理连续区间问题还是非常好用的
今天的学习就到这里啦
不要走开，小遍持续更新中~~~~~
