滑动窗口——优选算法
个人主页：敲上瘾-CSDN博客
个人专栏：游戏、数据结构、c语言基础、c++学习、算法
目录
一.滑动窗口算法原理：
二.无重复字符的最长子串
1.题目解析编辑
2.算法原理
3.代码编写
三.长度最小的子数组
1.题目解析
2.算法原理
3.代码编写
四.最小覆盖子串
1.题目解析
2.算法原理
3.代码编写
五.总结
一.滑动窗口算法原理：
滑动窗口可以说是一种特殊双指针算法，即它同样用两个指针实现。滑动窗口：用一个left指针和right指针来维护一段区间即[left, right]，也可称为窗口，right右移即进窗口，left右移即出窗口。即通常情况下left和right指针都是同向移动的。对于滑动窗口我们主要关心以下几点：
进窗口，出窗口，更新结果。进窗口肯定是在出窗口前进行的，而什么时候更新结果因题而异。
其实对于滑动窗口本身还是挺简单的，难点在我们能不能想到使用滑动窗口，接下来我准备了三个题，每题都分为三个步骤：题目解析，算法原理，代码编写。从最普通的暴力解法过渡到滑动窗口。最后来做总结。
二.无重复字符的最长子串
1.题目解析
该题需要我们求出字符串s内无重复字符的最长子串，注意这里子串的意思也就是在字符串s内连续的一段字符，所以在求解该题时最好不要对原字符串进行改动。
2.算法原理
明显这道题很容易想到的就是暴力枚举，但是时间复杂度比较高是过不了该题的测试的。在我们没能想到其他解法时，可以这样做，去分析暴力解法，从暴力解法中找到优化的规律。如下：
按以上方法把整个数组遍历完可以解决这个题目，但可以做以下优化：
这就是一个滑动窗口，把[left, right]区间当作一个窗口存放的是不重复的子串，然后用一个len变量来记录窗口的最大长度，当right滑动到字符串结尾时也就把所有的情况都记录了一遍，此时结束循环返回len该算法就完成了。
注意：这里因为要检查字符是否重复所以用一个哈希表来记录窗口内数据出现的个数可以提高效率。
3.代码编写
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
if(s.size()==0) return 0;
int len=-1;
int arr[127]={0};
for(int left=0,right=0;right<s.size();right++)
{
arr[s[right]]++;
cout<<arr[s[right]]<<' ';
while(arr[s[right]]==2)
{
arr[s[left++]]--;
}
if(len<right-left+1) len=right-left+1;
}
return len;
}
};三.长度最小的子数组
1.题目解析
本题要求子数组（即数组内的一段连续的元素）的元素之和大于等于target的最小长度，如果不存在返回0。例如示例1，[2,3,1,2,4,3]中子数组大于等于target的子数组有：
[2，3，1，2]，[2，3，1，2，4]，[2，3，1，2，4，3]，[3，1，2，4]，
[3，2，1，4，3]，[1，2，4]，[1，2，4，3]，[2，4，3]，[4，3]。
而长度最小的子数组为[4，3]，长度为2，以上所列的子数组是一个模拟暴力枚举的结果。
2.算法原理
该题可以使用暴力枚举（即两个循环解决）时间复杂度为O(N^2)。对于暴力解法在这里就不再多讲，现在我们可以试图从暴力解法中寻找规律并进行优化。如下：
以上我们分析的结果就是一个滑动窗口算法，left，right来维护这个窗口，left右移即出窗口，right右移即进窗口，当窗口里的元素之和大于等于target时更新最小长度。直到right滑动到数组结尾可得到答案。时间复杂度为O(N)。
3.代码编写
class Solution
{
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int left=0,right=0;
int sum=0,len=0;
while(right<nums.size())
{
sum+=nums[right];//进窗口
while(sum>=target)
{
int ln=right-left+1;//计算窗口长度
if(len==0||len>ln) len=ln;//更新len
sum-=nums[left++];//出窗口
}
right++;
}
return len;
}
};四.最小覆盖子串
1.题目解析
题目意思是给一个字符串s和t，要求在字符串s中找一个子串，这个子串要满足两点：(1)涵盖t字符串里的所有字符（包括重复字符），(2)最短的一个子串。注意：这个子串的要求不是涵盖t字符串，而是涵盖t字符串中的所有字符，这两者是有区别的。如示例1到3。
2.算法原理
同样这题也是可以使用暴力枚举的，我们还是从暴力枚举中去寻找规律并优化。
分析到此处，我们可以发现解题思路和上题可以说几乎是一模一样，但该题真正的难点并不是在此处。而在于我们如何去判断子串中是否包含t中的所有字符。
因为这里对子串中t的字符并没每有顺序要求，只要个数对上就行了，所以我们很自然地可以想到使用哈希表（此题使用数组充当哈希表更为高效）来记录数据出现个数。具体怎么判断呢？
使用两个哈希表分别记录t中的字符以及个数和子串（窗口）中字符以及出现个数。然后使用遍历的方式去匹配并判断。这样确实行得通，不过涉及遍历时间复杂度一下子就上来了。在这里我给大家分享一个小技巧，是官方题解上没有的。同样我们用这两个哈希表，但不用遍历去匹配判断，而是使用一个count变量记录子串（窗口）中有效字符的个数，
进窗口：当子串中某字符的个数与t字符串中对应字符个数相等时（用哈希表判断），有效字符count++。
更新结果并出窗口：当count等于t中的字符种类数时，判断并更新结果，当出窗口的元素为有效元素时（哈希表判断）count--。
3.代码编写
class Solution
{
public:
string minWindow(string s, string t)
{
string str;//储存最终结果
if(s.size()<t.size()) return str;
int hash1[128],hash2[128];
int len=0;
for(auto ch:t) if(hash1[ch]++==0) len++;
int minlen=INT_MAX,begin=-1;//minlen记录最小子串长度，begin记录子串开始的位置
for(int left=0,right=0,count=0;right<s.size();right++)
{
char in=s[right];
hash2[in]++;
if(hash2[in]==hash1[in]) count++;
while(count==len)//更新并出窗口
{
if(right-left+1<minlen)
{
minlen=right-left+1;
begin=left;
}
char out=s[left];
if(hash2[out]==hash1[out]) count--;
hash2[out]--;
left++;
}
}
if(begin==-1) return "";
return s.substr(begin,minlen);
}
};五.总结
相对于暴力解法而言滑动窗口本质其实是减少不必要的枚举，那么当我们做题时一眼看不出可以使用滑动窗口或者知道要使用滑动窗口但不知道如何用的时候，我们就可以从暴力枚举的角度出发，从暴力中的寻找规律并优化。
1.滑动窗口算法的使用场景
1.1.连续子数组问题
（1）固定窗口大小：例如，给定一个数组和窗口大小，求窗口内元素的和、最大值、最小值等。
（2）可变窗口大小：例如，在一个数组中找到和为某一特定值的子数组，需要根据条件动态调整窗口的左右边界。
1.2.字符串子串问题
例如，在一个字符串中查找包含特定字符集合的最短子串，或者判断一个字符串是否包含另一个字符串的排列等。
2.滑动窗口算法的基本步骤
2.1. 扩展窗口
移动右指针来扩大窗口，直到窗口满足特定的条件或者达到数组/字符串的边界。在每次移动右指针时，更新窗口的状态变量。
2.2. 收缩窗口
当窗口满足特定条件后，开始移动左指针来收缩窗口，同时继续更新窗口的状态变量。收缩窗口的过程是为了找到满足条件的最小窗口或者统计所有满足条件的窗口。
2.3. 更新结果
根据窗口的状态和问题的要求，更新最终的结果，结果可能是窗口的大小、窗口内元素的某种统计值等。