网站全屏大图代码,互联网舆情,信息化建设 网站,怎样做一个自己的网站滑动窗口本质其实也是一种双指针算法#xff0c;只是因为它维护的区间随着遍历的进行在不停变化#xff0c;所以形象地称为“滑动窗口”
一、⻓度最⼩的⼦数组 题目要求找到满足条件的长度最小的子数组#xff0c;我们先来想想暴力的做法#xff0c;再来想想能不能优化只是因为它维护的区间随着遍历的进行在不停变化所以形象地称为“滑动窗口”
一、⻓度最⼩的⼦数组 题目要求找到满足条件的长度最小的子数组我们先来想想暴力的做法再来想想能不能优化一般来说这种找子数组的暴力就是两层for循环枚举左右两个端点找到符合条件的所有子数组然后找出最小值下面画个图给大家分析一下 代码如下
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ansnums.size()1;for(int left0,right0,s0;rightnums.size();right){//进窗口snums[right];//判断是否需要出窗口while(starget){//更新答案ansmin(ans,right-left1);s-nums[left];}}return ansnums.size()1?0:ans;}
};
通过这道题我们就能总结出一些规律滑动窗口的题目分为三个步骤进窗口判断是否出窗口以及何时更新答案当然前提是你得先判断出这题是用滑动窗口解 二、将x减到0的最⼩操作数 这题如果你开始模拟左右两个区间之和x而没有想过转化条件那它就会很难解决但是其实题目可以等价成找元素和sum(nums)-x的最长子数组的长度最后用数组长度减去最长子数组长度就能得到最小操作数而等价后的题目明显和上一道题几乎一样这里就不具体分析了
代码如下
class Solution {
public:int minOperations(vectorint nums, int x) {int nnums.size();int targetaccumulate(nums.begin(), nums.end(), 0)-x;if(target0) return -1;//注意判断边界条件int ansn1;for(int left0,right0,s0;rightnums.size();right){//进窗口snums[right];//判断是否出窗口while(starget) s-nums[left];//更新答案if(starget) ansmin(ans,n-(right-left1));}return ansn1?-1:ans;}
};
好经过上面的题目我们就已经对滑动窗口的题目更多的认识和了解关键在于发现题目可以用滑动窗口解决以及维护区间的某些属性同时两个指针往同一方向移动(即满足某种单调性)---滑动窗口的特征 三、⽔果成篮 这道题目就是维护区间内水果类型是否大于2思路如下 进窗口-判断是否出窗口-更新答案 的细节在下面的代码里(请细品)
class Solution {
public:int totalFruit(vectorint fruits) {int nfruits.size(),ans0;int cnt[n];memset(cnt,0,sizeof(cnt));for(int left0,right0,s0;rightn;right){//进窗口if(cnt[fruits[right]]1)//出现次数为1次说明水果种类增加s1;//判断是否出窗口while(s2){if(--cnt[fruits[left]]0)//出现次数为0次说明水果种类减少s-1;}ansmax(ans,right-left1);}return ans;}
}; 四、找到字符串中所有字⺟异位词 这题跟上面几题不太一样这题的窗口长度是固定的就是查看字符串s中p.size()的窗口有几个是和组成p的字符一样记录下标步骤还是 进窗口-判断是否出窗口-更新答案
代码如下
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorintans;int hash1[26]{0},hash2[26]{0},kp.size(),cout0;for(int i0;ip.size();i)hash1[p[i]-a];for(int left0,right0;rights.size();right){//进窗口char ins[right];//如果加完之后该字符的数量任然p中该字符的数量说明增加的是有效字符coutif(hash2[in-a]hash1[in-a]) cout;//出窗口if(right-left1k){char outs[left];//如果该字符的个数本就p中该字符的数量说明减少的是有效字符cout--if(hash2[out-a]--hash1[out-a])cout--;}//更新答案if(kcout) ans.push_back(left);}return ans;}
}; 总结牢记滑动窗口的三个步骤进窗口判断是否出窗口以及何时更新答案稍难的滑动窗口一般都是和哈希表结合起来主要是在判断进窗口和出窗口的条件上下文章当然一切的前提是你能想到用滑动窗口来解决问题当问题和维护一段连续区间的属性有关时我们就可以想一想滑动窗口
