当前位置: 首页> 游戏> 手游 > 滑动窗口算法

滑动窗口算法

时间:2025/7/10 4:18:25来源:https://blog.csdn.net/2401_82494141/article/details/141228712 浏览次数:0次

长度最小的子数组

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://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的最短子序列

这个时候,我们往往会在遍历时比较(打擂台)。

关键字:滑动窗口算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: