👀樊梓慕：个人主页
🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
🌝每一个不曾起舞的日子，都是对生命的辜负
目录
前言
1.长度最小的子数组
滑动窗口类问题解题思路大纲：
2.无重复字符的最长字串
3.最大连续1的个数Ⅲ
4.将 x 减到 0 的最小操作数（medium）
前言
本篇文章主要会讲解滑动窗口的解题思想，滑动窗口实际上就是利用双指针的基础思想，并且利用单调性进行解题的方法。
滑动窗口所用到的双指针是用来维护这个所谓的『 窗口』，所以这两个指针是『 同向』且『 不回退』的，这也就决定了滑动窗口解题的时间复杂度最多为O(2N) 即O(N)，所以滑动窗口是一种非常优秀的算法思想。
那么滑动窗口思想具体的应用，以及如何分析判断是否适用滑动窗口解题呢？
欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================文章来源地址https://www.toymoban.com/news/detail-825716.html
GITEE相关代码：🌟樊飞 (fanfei_c) - Gitee.com🌟
=========================================================================
1.长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
如果依照暴力枚举的策略，解题思路大致如下：
利用双指针，一个指针固定，移动另一个指针，当两个指针中间的所有元素和大于等于目标值target时，记录此时的长度，然后循环往复，求长度最小值。
代码如下：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 记录结果
int ret = INT_MAX;
int n = nums.size();
// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
// 枚举开始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 记录从这个位置开始的连续数组的和
// 寻找结束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 将当前位置加上
if (sum >= target) // 当这段区间内的和满⾜条件时
{
// 更新结果，start 开头的最短区间已经找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后结果
return ret == INT_MAX ? 0 : ret;
}
};可其实这其中有太多可以忽略掉的枚举区间，我们来分析一下：
本题要求的是长度最小子数组，所以此时一定是要更新left的位置即可，这就达到了不回退的目的。
注意：要在移动left之前更新结果。
所以此类问题，我们可以将left和right中间的区域看作一块窗口，该窗口不断的向后移动，直到right超出数组为止。
在这一过程中：
- right移动导致元素进入窗口的行为我们称为『 进入窗口』；
- left移动导致元素离开窗口的行为我们称为『 离开窗口』；
- 判断left和right维护的窗口是否满足题目条件我们称为『 判断』；
- 满足题目条件时更新结果的行为我们称为『 更新结果』。
所以以上这些步骤就构成了『 滑动窗口』类问题的解题思路。
滑动窗口类问题解题思路大纲：
①left=0,right=0；
②进入窗口；
③判断；
离开窗口；
④更新结果；
其中更新结果取决于具体的题目要求，『 就题论题』。
比如本题就需要在『 离开窗口』之前『 更新结果』。
有了思路，画图独立完成代码，不要直接看博主的代码。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left=0,right=0;
int size=nums.size();
int sum=0;
int len=INT_MAX;
while(right<size)
{
sum+=nums[right];//进入窗口
while(sum>=target)//判断
{
len=min(len,right-left+1);//更新结果
sum-=nums[left++];//离开窗口
}
right++;
}
return len == INT_MAX ? 0 : len;
}
};2.无重复字符的最长字串
3. 无重复字符的最长子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。
其实滑动窗口类题目最重要的是弄清楚『 为什么』要使用滑动窗口，而不是『 怎样』适用滑动窗口。
像本题，你是如何分析出要使用滑动窗口的呢？
首先依据暴力枚举的策略，同样固定一个指针，移动另一指针，搭配哈希表得到最长字串：
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;
}
};注意：因为题目说明都为字符，所以我们可以创建一个128大小的数组用来模拟哈希表，没有必要真的申请一个哈希表出来。
然后才能依据这一暴力枚举的底子我们做优化。
思路：
当right指向重复字符时，我们是否需要直接让right回退，left++呢？
其实如果right指向重复字符了，那么就证明此时就是left开头代表的窗口的最长字串了（因为在这之前right没有指向重复字符），所以此时不需要移动right，而应该移动left直到没有重复字符为止，然后再移动right即可。
- 如果这个字符出现的频次超过1 ，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到这个元素的频次变为1，然后再更新结果。
- 如果没有超过1 ，说明当前窗口没有重复元素，可以直接更新结果。
所以『 更新结果』我们可以统一放在『 判断』的外面。
有了思路，画图独立完成代码，不要直接看博主的代码。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128]={0};
int left=0,right=0,len=0;
int n=s.size();
while(right<n)
{
hash[s[right]]++;//进入窗口
while(hash[s[right]]>1)//判断
hash[s[left++]]--;//离开窗口
len=max(len,right-left+1);//更新结果
right++;
}
return len;
}
};3.最大连续1的个数Ⅲ
1004. 最大连续1的个数 III - 力扣（LeetCode）https://leetcode.cn/problems/max-consecutive-ones-iii/description/
给定一个二进制数组
nums和一个整数k，如果可以翻转最多k个0，则返回 数组中连续1的最大个数 。
虽然题目中说是要翻转数字，但我们要的最终结果与翻转无关，何况如果真的实现翻转反而变得复杂，所以这里我们没有必要真的翻转。
仔细阅读题目，其实就是求数组中⼀段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。
既然是连续区间，可以考虑使用『 滑动窗口』来解决问题。
思路：
设置一个 0 计数器 zero。
如果 right 遇到 0，我们应该让 zero ++ ，如果 right 遇到 1，直接跳过即可，这就是『 进入窗口』。
判断什么呢？当然是『 判断』zero是否超过 k，如果超过 就『 离开窗口』，每轮『 更新结果』。
有了思路，画图独立完成代码，不要直接看博主的代码。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0,right=0,zero=0;
int n=nums.size();
int ret=0;
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;
}
};4.将 x 减到 0 的最小操作数（medium）
1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
给你一个整数数组
nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将
x恰好 减到0，返回 最小操作数 ；否则，返回-1。
阅读题目后，我们发现解决方案可能比较复杂，因为既有可能从左面，也有可能从右面，还有可能一左一右等等，这么多复杂的情况，所以我们需要尝试对问题做转化，这也就是『 正难则反』的思路。
如上图，我们可以求 target 这一区域最长时，那么此时就对应着最小操作数，最小操作数就等于数组元素个数减去target区域的元素个数。
所以我们成功转化出『 滑动窗口』问题。
- 如果 sum < target ，右移右指针，直至变量和大于等于 target ，或右指针已经移到头；
- 如果 sum > target ，右移左指针，直至变量和小于等于 target ，或左指针已经移到头；
- 如果经过前两步的左右移动使得 sum == target ，维护满足条件数组的最大长度，并让下个元素进入窗口；
有了思路，画图独立完成代码，不要直接看博主的代码。
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;//处理细节
int left=0,right=0,tmp=0;
int n=nums.size();
int 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 len;
else return n-len;
}
};=========================================================================
如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容
🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏＋关注 ~🌟文章来源：https://www.toymoban.com/news/detail-825716.html
=========================================================================
到了这里，关于【算法】基础算法002之滑动窗口（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
