假期算法提升（带你彻底掌握滑动窗口）
呀哈喽，我是结衣。
今天我们要学习的是一种新的算法，也是一种双指针。不过他拥有一个全新的名字”滑动窗口“。
文章目录
- 1.长度最小的子数组（medium）
- 思路
- 解题方法
- Code
- 2.无重复字符的最长子串（medium）
- 思路
- 解题方法
- Code
- 3.最大连续1的个数 III（medium）
- 思路
- 解题方法
- Code
- 4.将x减到0的最小操作数（medium）
- 思路
- 解题方法
- Code
- 5.水果成篮（medium）
- 思路
- 解题方法
- Code
- 6.找到字符串中所有字母异位词（medium）
- 思路
- 解题方法
- 方法一（直接比较哈希表）
- Code
- 方法二（更优）
- Code
- 7.串联所有单词的子串（hard）
- 思路
- 解题方法
- Code
- 8.最小覆盖子串（hard）
- 思路
- 解题方法
- Code
- 总结规律
1.长度最小的子数组（medium）
题目链接：长度最小的子数组
题目描述：
思路
因为数组元素全为正整数，使得数组具有了一种单调性。以示例1为例子，2+3+1+2会大于7，那么我们好有必要继续向后遍历吗？没有必要，所以我们就会想到去掉前面的一个数变成3+1+2这样也就小于7啦，于是我们就继续遍历数组，3+1+2+4又会大于7了我就重复刚刚的操作，我们遍历完数组。
解题方法
又上面的思路我们可以想到定义两个指针left和right，right来遍历数组，left在后面跟着，是双指针不过有了新的名字“滑动窗口”
在图中我可以看到right和left共同维护着一段区间，而且right和left又可以移动，顾名思义就是滑动窗口
滑动窗口最重要的操作就是进窗口（移动right）判断 出窗口（移动left） 更新结果。
只要这几步就可以做出题目来。
要注意的数更新结果的位置是不确定的，要根据具体的题目要求。
Code
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0,n = nums.size();
int len = INT_MAX;
for(int left = 0,right = 0;right<n;right++)//right++为进窗口
{
sum+=nums[right];
while(sum>=target)//判断
{
len = min(len,right-left+1);//更新结果
sum-=nums[left];
left++;//出窗口
}
}
return len==INT_MAX?0:len;
}
};
2.无重复字符的最长子串（medium）
题目链接：无重复字符的最长子串
题目描述：
思路
当我们不知道怎么写之前，我们可以运用暴力的方法先考虑问题。遍历字符串时（示例1），当我们遍历到第二个a时我们此时就出现了重复的字符，我们可以继续遍历，但那就没有必要了。我们可以重新遍历从第二个字符开始，再向后举行遍历，这样的化时间复杂度肯定就是O（N^2）了这就是暴力，但是我不要忘了应该怎么判断重复字符，看肯定看的出来，可是对于计算机我们就要记录一下字符了，所以我们就要运用到哈希表了。
解题方法
对于思路中的暴力解法，我们是可以做到很多优化的，运用“滑动窗口”，使得时间复杂度变为O（N）。
我们利用“滑动窗口”，来保证窗口中的元素一定不会重复就可以了，为了实现这个操作我们需要定义应该哈希表。因为这里的数据全是字符，所以我们可以用int数组来映射就可以了。
然后就是滑动窗口的经典操作：
滑动窗口最重要的操作就是进窗口（移动right）判断 出窗口（移动left） 更新结果。
Code
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
int len = 0;
int hash[128] = {0};
for(int left = 0,right = 0;right<n;++right)//进窗口
{
hash[s[right]]++;
while(hash[s[right]]>1)
{
hash[s[left]]--;
left++;//出窗口
}
len = max(len,right-left+1);//更新结果
}
return len;
}
};
3.最大连续1的个数 III（medium）
题目链接：最大连续1的个数 III
题目描述：
思路
如果我们只是寻找最长的子字符串1，要考虑的东西就太多了。为了让这个题目更加的简单，我们应该采用一种正难则反的思想，我们把问题转化为寻找不超过k个0的最长子串。这样做就简单的多了，所以在写编程题的时候如果一点想法都没有不妨换个角度来想问题。
解题方法
当我们把问题简化之后，滑动窗口的想法就呼之欲出了，和前面一样，我们要做的就是维护窗口里的元素。这次呢，我们要维护的就是窗口内0元素不能超过k个。在此基础上我们再运用滑动窗口的公式就可以解决问题了：进窗口（移动right）判断 出窗口（移动left） 更新结果。
Code
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
//正难则反，我们把问题转化为寻找不超过k个0的最长子串。
int zero = 0,len = -1;
for(int left = 0,right = 0;right<nums.size();++right)//进窗口
{
if(nums[right]==0) zero++;
while(zero>k)//条件判断
{
if(nums[left]==0) zero--;
left++;//出窗口
}
if(zero == k)len = max(len,right-left+1);//更新结果
}
return len==-1?nums.size():len;
}
};
4.将x减到0的最小操作数（medium）
题目链接：将x减到0的最小操作数
题目描述
思路
同样的，直接写太麻烦了，要考虑的东西太过。还是正难则反，把问题转化一下不就变成了求目标值为sum-x最长子数组和，和第一题不就差不多了吗？
解题方法
和第一题类似，运用滑动窗口解决，不过再滑动窗口操作之前我们要判断一下sum-x是否为负数如果为负数的话，后面代码就会溢出的。了解完成后还是那四步：进窗口（移动right）判断 出窗口（移动left） 更新结果。
Code
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
//正难则反，表面上让你找让x减小到0的最小操作数，实际是可以转化为求目标值为sum-x最长子数组和。
int sum = 0;
for(auto num:nums) sum+=num;
int tar = sum-x;
if(tar<0)
return -1;
int sum_ = 0,res = -1;
for(int left = 0,right = 0;right<nums.size();++right)//进窗口
{
sum_+=nums[right];
while(sum_>tar)//条件判断
{
sum_-=nums[left++];//出窗口
}
if(sum_==tar) res = max(res,right-left+1);//结果更新
}
return res == -1?res: nums.size()-res;
}
};
5.水果成篮（medium）
题目链接：水果成篮
题目描述：
思路
这道题的题目有点长，把他翻译翻译就是求最长不超过两类树的子数组。了解的这个，这道题就变得简单了。至于如何判断是否超过了两类树，又要用到哈希表了。
解题方法
写题的关将就在于理解题目，我们要把题目转化成我们熟悉的题目。就像这道题，转化后就自然而然地想到了我们滑动窗口。不过就是再加上一个哈希表。我们建立一个哈希数组，在建立一个kinds来判断窗口内树地种类。如何判断呢？
Code
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//题目可能有点难懂，翻译一下就求最长不超过两类树的子数组。
int hash[100001] = {0};
int kinds = 0,n = fruits.size(),len = 0;
for(int left = 0,right = 0;right<n;++right)//进窗口
{
if(hash[fruits[right]]++==0) kinds++;
while(kinds>2)//条件判断
{
if(--hash[fruits[left]]==0) kinds--;
left++;//出窗口
}
len = max(len,right-left+1);//更新结果
}
return len;
}
};
6.找到字符串中所有字母异位词（medium）
题目链接：找到字符串中所有字母异位词
题目描述：
思路
刚上手可能没想法，那就尝试暴力解法吧，依次遍历字符串以示例1为例。
暴力加哈希可以解决但时间复杂度太高。
解题方法
优化上面的暴力方法就需要滑动窗口了。不过这里我们着重要讲的是如何利用哈希表来出来这种情况。我们定义了两个哈希表。一个哈希1用来存放p字符串中的字符。哈希表2就用来存放s字符串里的字符。我们该如何判断窗口内的元素都是p中的呢？
方法一（直接比较哈希表）
因为字符串都是小写字母，每次我们窗口里有p.size()的字符时我们就比较两个哈希表，虽然每次比较都要遍历哈希表，但是小写字母只有26个时间复杂度度也就O（26*n）也是常数级别的可以忽略。
Code
class Solution {
public:
bool check(vector<int>hash,vector<int>hash_1)
{
for(int i = 0;i<26;++i)
{
if(hash[i]!=hash_1[i]) return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
int n_p = p.size();
vector<int> hash_1(26,0);
for(auto tmp:p) hash_1[tmp-'a']++;
int n = s.size();
int left = 0,right = 0;
vector<int>hash(26,0);
vector<int>res;
while(right<n)
{
hash[s[right]-'a']++;
if(right>=n_p-1)
{
if(check(hash,hash_1))
res.push_back(left);
hash[s[left]-'a']--;
left++;
}
right++;
}
return res;
}
};
方法二（更优）
我们利用一个count来记录窗口内p中字符串的个数。是p中的字符count就++，后续的出窗口也是如此，是p中的字符就count–。 这个方法的时间复杂度就是O(N)了
Code
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash_1[26] = {0};
int hash[26] = {0};
for(auto ch:p) hash_1[ch-'a']++;
int count = 0,n = s.size();
vector<int> res;
for(int left = 0,right = 0;right<n;++right)//进窗口
{
if(++hash[s[right]-'a']<=hash_1[s[right]-'a']) count++;
if(right-left+1>=p.size())//条件判断
{
if(count==p.size()) res.push_back(left);//更新结果
if(hash[s[left]-'a']--<=hash_1[s[left]-'a']) count--;
left++;//出窗口
}
}
return res;
}
};
7.串联所有单词的子串（hard）
题目链接：串联所有单词的子串
题目描述：
思路
这题和上面的那道题是差不多的，把字符改成了字符串了，这样的话我们之前的数组映射就不好用了。但是我们可以借助一个容器unordered_map。不过还有一点的不同，我们遍历的次数发生了改变。
解题方法
在次数上的改变体现在因为现在是字符串了。len（word[0].size()）
还要注意的就是因为现在是字符串，所以我们的right和left可就是加len个长度了。
Code
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string,int> hash_1;
for(auto tmp:words) hash_1[tmp]++;
int len = words[0].size(),n = s.size();
vector<int>res;
for(int i = 0;i<len;++i)
{
unordered_map<string,int> hash;
int count = 0;
for(int left = i,right = i;right+len<=n;right+=len)//入窗口
{
string in = s.substr(right,len);
if(hash_1[in]&&++hash[in]<=hash_1[in]) count++;
if(right-left+len>=words.size()*len)//条件判断
{
if(count==words.size()) res.push_back(left);//结果更新
string out = s.substr(left,len);
if(hash_1[out]&&hash[out]--<=hash_1[out]) count--;
left+=len;//出窗口
}
}
}
return res;
}
};
8.最小覆盖子串（hard）
题目链接：最小覆盖子串
题目描述：
思路
和前面两题类似，大体上的步骤都一样。
解题方法
可以和前面两题用相似的写法，定义两个哈希表。然后用count来判断窗口内是否包含全部的t中元素。虽然我们的返回条件变啦。但是我们也可以不需要创建一个string来存储最小的覆盖子串，我们可以利用substr这个成员函数，只需要我们记录一下初始的位置和长度就可以了。来试试吧。
Code
class Solution {
public:
string minWindow(string s, string t) {
int hash_1[128] = {0};
int hash[128] = {0};
for(auto ch:t) hash_1[ch]++;
int n = s.size(),count = 0,len = INT_MAX,begin = 0;
for(int left = 0,right = 0;right<n;++right)//进窗口
{
if(++hash[s[right]]<=hash_1[s[right]]) count++;
while(count>=t.size())//条件判断
{
int old = len;
len = min(len,right-left+1);//结果更新
if(old!=len) begin = left;
if(hash[s[left]]--<=hash_1[s[left]]) count--;
left++;//出窗口
}
}
return len==INT_MAX?"":s.substr(begin,len);
}
};
总结规律
不知道你有没有发现，我们的滑动窗口的代码都差不多。我也是把每一道题都重新写了一遍然后写成了一样的格式。
for(int left = 0,right = 0;right<n;++right)//进窗口
{
if(++hash[s[right]]<=hash_1[s[right]]) count++;
while(count>=t.size())//条件判断
{
int old = len;
len = min(len,right-left+1);//结果更新
if(old!=len) begin = left;
if(hash[s[left]]--<=hash_1[s[left]]) count--;
left++;//出窗口
}
}
全是一层for循环来遍历数组，里面的判断肯是while循环也可能是if这取决于你要判断的次数，然后我们的出窗口都是在判断里面的，至于结果更新只有他的位置是变化的，所以我们在写代码前就要看看结果在哪里更新，这样的话滑动窗口的问题就都可以解决了。
那么本篇博客就到这里结束了，如果存在错误希望得到您的指正。
完
