长度最小的子数组
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/minimum-size-subarray-sum/
算法思想
注：黑色区间为临界子区间
图解：
有上图容易知道，找到临界子区间后，左指针会向右走；如果想让窗口有可能大于等于target，右指针不能往左走（因为这样的区间一定小于target）。
流程：
1.右指针入窗口
2.while（看窗口是否大于target）->更新结果，左指针出窗口
代码实现：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=INT_MAX,sum=0,size=nums.size();for(int l=0,r=0;r<size;++r){sum+=nums[r];while(sum>=target) {ans=min(ans,r-l+1);sum-=nums[l++];}}return ans==INT_MAX?0:ans;}
};无重复字符的最长子串
. - 力扣（LeetCode）
算法思想：
注：黑色区间为临界子区间
图解:
有上图容易知道，找到临界子区间后，左指针会向右走；因为重复元素是in，其他元素是不重复的，所以在in出窗口前，这些左指针一定要走到右指针处，所以右指针就不用往回走了
注意：这些左指针一定没有临界子区间大，所以这些元素都无效,直接出窗口
流程：
1.右指针入窗口
2.while(in还没有出窗口) ->左指针出窗口
3.更新结果
代码实现：
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0},size=s.size(),ans=0;for(int l=0,r=0;r<size;++r) {char in = s[r]; ++hash[in];while(hash[in]>=2) {char out = s[l++]; --hash[out];}ans = max(ans,r-l+1);}return ans;}
};最大连续1的个数III
. - 力扣（LeetCode）
算法思想：
与上一题同一模型，本处略……
代码实现：
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zeros=0,size=nums.size(),ans=0;for(int l=0,r=0;r<nums.size();++r) {if(nums[r]==0) ++zeros;while(zeros>k) if(nums[l++]==0) --zeros;ans=max(ans,r-l+1);}return ans;}
};将x减到0的最小操作数
. - 力扣（LeetCode）
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(const auto& e : nums) sum+=e;int k=sum-x,size=nums.size(),ans=-1,sum1=0;if(k<0) return -1;for(int l=0,r=0;r<size;++r) {sum1+=nums[r];while(sum1>k) sum1-=nums[l++];if(sum1==k) ans=max(ans,r-l+1);}if(ans==-1) return -1;else return size-ans;}
};算法思想：
图解：
这种窗口长度为0，一般视作窗口不存在，但用抽象的角度思考，他可以看作是一个什么都没有，长度为0，右指针在左指针左边的窗口
思路： 正难则反
这里的问题可以转化为找到一个最长的，值为sum-x(记作k)的子区间
注意：sum-x<0的情况直接过滤，这种情况不存在
sum==0的子区间是可以找到的
流程：
1.右指针入窗口
2.while(sum1>k)->左指针出窗口
3.if(sum1==k)->更新结果
代码实现：
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(const auto& e : nums) sum+=e;int k=sum-x,size=nums.size(),ans=-1,sum1=0;if(k<0) return -1;for(int l=0,r=0;r<size;++r) {sum1+=nums[r];while(sum1>k) sum1-=nums[l++];if(sum1==k) ans=max(ans,r-l+1);}if(ans==-1) return -1;else return size-ans;}
};水果成蓝
算法思想：
流程：
1.右指针入窗口
2.while(count>2) 左指针出窗口
3.更新结果
代码实现：
1.优化版本：
class Solution {
public:int totalFruit(vector<int>& fruits) {int size=fruits.size(),kinds=0,ans=0;vector<int> hash; hash.resize(size,0);for(int l=0,r=0;r<size;++r) {int in=fruits[r]; if(hash[in]++==0) ++kinds;while(kinds>2) {int out=fruits[l++];if(--hash[out]==0) --kinds;}ans=max(ans,r-l+1);}return ans;}
};2.普通版本：
class Solution {
public:int totalFruit(vector<int>& fruits) {int size=fruits.size(),kinds=0,ans=0;unordered_map<int,int> hash;for(int l=0,r=0;r<size;++r) {int in=fruits[r]; hash[in]++;while(hash.size()>2) {int out=fruits[l++];if(--hash[out]==0) hash.erase(out);}ans=max(ans,r-l+1);}return ans;}
};找到字符串中所有字母异位词
. - 力扣（LeetCode）
方法一：利用滑动窗口枚举所有的包含目标字符串的子串，再筛选出字符串长度一样的子串
思路1：控制内容
注释：我们称包含目标字符串的子串为【目标】
找到一个【目标】后，左指针向右移动一步，右指针不会往回走，它一定会走到当前位置。
流程：
1.入窗口
2.while(count==size)->更新结果，出窗口
代码实现：
class Solution {
public:vector<int> findAnagrams(string s, string p) {int hashp[26]={0};for(const auto& e : p) ++hashp[e-'a'];int hashs[26]={0},size=s.size(),count=0;vector<int> ans;for(int l=0,r=0;r<size;++r) {char in=s[r]; if(++hashs[in-'a']<=hashp[in-'a']) ++count; while(count==(int)p.size()) {if(count==r-l+1) ans.push_back(l); char out=s[l++];if(hashs[out-'a']--<=hashp[out-'a']) --count;}}return ans;}
};思路2：控制长度
注释：我们称和目标字符串长度相同的子串为【目标】
找到一个【目标】后，左指针和右指针同时移动。
流程：
1.入窗口
2.if(长度相等) ->更新结果，出窗口
代码实现：
class Solution {
public:vector<int> findAnagrams(string s, string p) {int hashp[26]={0};for(const auto& e : p) ++hashp[e-'a'];int hashs[26]={0},size=s.size(),count=0,sizep=p.size();vector<int> ans;for(int l=0,r=0;r<size;++r) {char in=s[r]; if(++hashs[in-'a']<=hashp[in-'a']) ++count; if(r-l+1==sizep) {if(count==sizep) ans.push_back(l);char out=s[l++];if(hashs[out-'a']--<=hashp[out-'a']) --count;}}return ans;}
};串联所有单词的字串
. - 力扣（LeetCode）
找到字符串中所有字母异位词中思路2，思路1也是OK的。
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ans;int sizes = s.size(),sizew=words.size(),len=words[0].size();unordered_map<string,int> hashw;for(const auto& e : words) ++hashw[e];for(int i=0;i<len;++i) {int count=0;unordered_map<string,int> hashs;for(int left=i,right=i;right+len<=sizes;right+=len) {string in=s.substr(right,len);++hashs[in];if(hashw.count(in)&&hashs[in]<=hashw[in]) ++count;if((right-left)/len+1==sizew) {if(count==sizew) ans.push_back(left);string out=s.substr(left,len);if(hashw.count(out)&&hashs[out]<=hashw[out]) --count;--hashs[out];left+=len;}}}return ans;}
};最小覆盖子串
找到字符串中所有字母异位词中思路1.
class Solution {
public:string minWindow(string s, string t) {int hashp[128]={0};for(const auto& e : t) ++hashp[e];int hashs[128]={0},size=s.size(),count=0;int begin=-1,end;for(int l=0,r=0;r<size;++r) {char in=s[r]; if(++hashs[in]<=hashp[in]) ++count; while(count==(int)t.size()) {if(begin==-1||r-l+1<end-begin+1) {begin=l; end=r;}char out=s[l++];if(hashs[out]--<=hashp[out]) --count;}}string ans;if(begin==-1) return "";ans=s.substr(begin,end-begin+1);return ans;}
};总结
1.滑动窗口使用前提：左指针向右走，右指针不用往回跑。
2.滑动窗口常用来解决：找到符合要求的连续子串。
2.1.滑动窗口可以找到序列中所有符合要求的连续子串。
例如：找到总和为100的所有子序列
2.2但题目往往这么问：
例如：找到总和为100的最短子序列
这个时候，我们往往会在遍历时比较（打擂台）。
