前言：

上篇我们介绍了双指针算法，并结合具体题目进行了详细的运用讲解。本篇我们将会了解滑动窗口。滑动窗口是一种常用的算法技巧，主要用于处理子数组、子串等具有“窗口”特性的题目。柳暗花明，乃巧解复杂问题的高效之道。

一. 长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目分析：

1. 题目要求寻找一个子数组，数组内所有元素相加之和大于等于target，且要求该子数组的长度最小

2. 如果找到则返回最小子数组的长度，如果没有找到则返回0

注意：题目中所给的数组内所有元素均为正整数，且target也为正整数！！！ 

思路讲解：

暴力解法（会超时）：

滑动窗口：

暴力解法超时的原因为进行了大量冗余的遍历。

我们需要明白，由于所有的元素均为正整数，当子数组的区间长度在原有基础下增大时，和必然增大，反之，则必然减小，即子数组区间和的大小与区间长度存在单调性。

假设 target = 7, nums = [2, 3, 1, 2, 4, 3]：

初始状态：left = 0, right = 0, sum = 2，窗口未达到 target。
入窗口：将 right 向右移动，直到窗口和 sum = 9，满足条件。
出窗口：移动 left，将子数组 [4, 3] 缩小到长度 2。

因此，其解法可总结为入窗口，出窗口，更新情况三大步骤。

如图：

代码实现：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum=0;//子数组的和int n=nums.size(),ret=INT_MAX;//由于是求最小值，因此可首先假定其为int的最大值for(int left=0,right=0;right<n;right++){sum+=nums[right];//进窗口while(sum>=target){ret=min(ret,right-left+1);sum-=nums[left++];}//出窗口，更新ret，为下一轮遍历做准备}return ret==INT_MAX?0:ret;}
};

优势分析：

1. 时间复杂度为O(n)，远远优于暴力解法

2. 在处理重复遍历问题时，我们直接采取改变窗口区间长度的方式，利用先前分析过的单调性，以left和right对其进行控制，使效率大大提高。

二.  无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目分析：

1. 题目要求找出一个无重复长度的子串，且该子串要求长度最长。

2. 子串的含义同子数组类似，一定要求连续，最大可为字符串本身。

思路讲解： 

暴力解法（不会超时，可以通过）：

枚举「从每⼀个位置」开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的。

可在往后寻找⽆重复⼦串能到达的位置时，利⽤「哈希表」统计出字符出现的频次，来判断什么时候⼦串出现了重复元素。

代码实现：

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;// 如果没有重复，就更新 retret = max(ret, j - i + 1);}}// 2. 返回结果return ret;}
};

 滑动窗口：

研究的对象子串仍旧是一段连续的区间，因此可以考虑使用滑动窗口来解决。

1. 我们可以使用哈希来进行字符的映射，由于窗口内所有元素都是不重复的，因此我们可以让右端元素进入窗口，并记录其字符出现频次。

2. 当字符出现频次不全为0时，即代表出现了重复元素，需要让左侧元素逐次出窗口，直至恢复频次全为0为止。

3. 当完全遍历后，此时窗口长度即为最长字串的长度。

代码实现：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};//模拟哈希表int n=s.size();int ret=0;for(int left=0,right=0;right<n;right++){hash[s[right]]++;//入窗口while(hash[s[right]]>1){hash[s[left++]]--;//出窗口}ret=max(ret,right-left+1);//更新子串长度}return ret;}
};

 三. 最大连续1的个数lll

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目分析：

1. 给定一个元素为1或0的数组，以及一个正整数K，可以在K的范围内把0变为1，求最长连续区间内均为1的长度。

2. 问题可转化为，求一段最长的连续区间，区间内0的个数在K范围内。

思路讲解：

滑动窗口：

此题仍为求一段连续区间的长度，因此也可以用滑动窗口来解决。

 1. 利用zere记录区间内0的个数，当zero小于K时，即可令右端元素进窗口

 2. 当zero>K时，需要令左端元素出窗口，如果左端元素为0，则令zero-1，直至zero<K为止。

3. 当完全遍历后，窗口长度即为最大连续区间的长度。 

代码实现：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zero=0;//记录0的个数int n=nums.size(),ret=0;for(int left=0,right=0;right<n;right++){if(nums[right]==0){zero++;}//记录0的增长情况while(zero>k){if(nums[left++]==0){zero--;}}//出窗口ret=max(ret,right-left+1);//更新窗口长度}return ret;}
};

小结：本篇介绍了滑动窗口的含义并结合基础题型加以讲解练习，下篇讲为大家分享滑动窗口的进阶题目，欢迎各位佬前来支持斧正！！！