算法入门（一）：滑动窗口 之 可变窗口-求最短 / 最长-数值计算 （Leetcode 209 / 713 / 2875 / 1004 / 2024）

可变窗口-求最短 / 最长

可变窗口的核心是维护一个始终满足条件的窗口：

• 扩展：一般来说都是向右，将最右侧的元素加入窗口做一些动作
• 收缩：到条件被破坏时，将最左侧的元素移除，直到条件重新满足
• 统计：统计一些窗口的数据，例如窗口长度
• 这类题目非常灵活，没有固定代码模板，只有思维模板！
  题目分两种类型：
• 纯数值的简单情况
• 字符串/哈希表/队列/栈/堆的复杂情况。
  

模板 / 思维方式

// 思维方式（理解这个逻辑）intleft=0;for(intright=0;right<n;right++){// 1. 扩展窗口：加入新元素窗口加入 nums[right];// 2. 收缩窗口：直到窗口重新满足条件while(窗口不满足条件&&left<=right){窗口移除 nums[left];left++;}// 3. 统计：此时窗口一定满足条件if(条件满足){统计当前窗口;}}

数值计算

Leetcode 209

该题没法使用模板，明确2 移除元素的动作 和3 统计量就可以了。

intminSubArrayLen(inttarget,vector<int>&nums){intn=nums.size();intminLen=INT_MAX;intwindowSum=0;intleft=0;intright=0;for(;right<n;right++){windowSum+=nums[right];while(windowSum>=target){//满足条件minLen=min(minLen,right-left+1);//更新结果windowSum-=nums[left];//更新窗口left++;//更新边界}}returnminLen<=n?minLen:0;}

Leetcode 713

遵循扩展，条件，统计的思考方式：

• 扩展： product *=nums[right];
• 条件：当积大于等于k的时候，窗口需要收缩；
• 统计：当积严格小于k的时候，统计该次right存在时的满足条件的长度，累加起来。

intnumSubarrayProductLessThanK(vector<int>&nums,intk){intn=nums.size();longlongproduct=1;intleft=0;intright=0;intres=0;for(;right<n;right++){product*=nums[right];while(product>=k&&left<=right){product/=nums[left];left++;}res+=right-left+1;}returnres;}

Leetcode 2875

Leetcode209的扩展题。
一般会考虑两轮就覆盖所有情况，于是数组下标采取 % n 取mod：

classSolution{public:intminSizeSubarray(vector<int>&nums,inttarget){intn=nums.size();intsum=0;intleft=0;intright=0;intres=INT_MAX;for(;right<n*2;right++){sum+=nums[right%n];while(left<=right&&sum>target){sum-=nums[left%n];left++;}if(sum==target)res=min(res,right-left+1);}returnres==INT_MAX?-1:res;}};

可惜只能通过 80 %的用例。

如果情况是[1,2]，target = 7，[1,2,1,2,1,2,1,2…]，需要大于两组的和才能得到targer ，所以不能只在 2n 范围内搜索。
接下来要做出修改：

• 判断条件：是否等于 target 变更为 target % total
• 答案：res需要加上 target / total * n ，即多出来的组数 x 每一组的数量 。

classSolution{public:intminSizeSubarray(vector<int>&nums,inttarget){//1. 计算总和longlongtotal=0;for(intnum:nums)total+=num;//2. 滑动窗口,判断条件全部变为取模intn=nums.size();intsum=0;intleft=0;intright=0;intres=INT_MAX;for(;right<n*2;right++){sum+=nums[right%n];while(left<=right&&sum>target%total){sum-=nums[left%n];left++;}if(sum==target%total)res=min(res,right-left+1);}//3. 结果记得也加上取模的变化returnres==INT_MAX?-1:res+target/total*n;}};

Leetcode1004 / 2024

Leetcode1004 / 2024 是同一种题目： nums[]只有两种元素的情况下，如何使用滑动窗口。