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

📅 2026/6/30 23:38:36 👁️ 次浏览

算法入门一滑动窗口之可变窗口-求最短 / 最长-数值计算 Leetcode 209 / 713 / 2875 / 1004 / 2024可变窗口-求最短 / 最长模板 / 思维方式数值计算Leetcode 209Leetcode 713Leetcode 2875Leetcode1004 / 2024可变窗口-求最短 / 最长可变窗口的核心是维护一个始终满足条件的窗口扩展一般来说都是向右将最右侧的元素加入窗口做一些动作收缩到条件被破坏时将最左侧的元素移除直到条件重新满足统计统计一些窗口的数据例如窗口长度这类题目非常灵活没有固定代码模板只有思维模板题目分两种类型纯数值的简单情况字符串/哈希表/队列/栈/堆的复杂情况。模板 / 思维方式// 思维方式理解这个逻辑intleft0;for(intright0;rightn;right){// 1. 扩展窗口加入新元素窗口加入 nums[right];// 2. 收缩窗口直到窗口重新满足条件while(窗口不满足条件leftright){窗口移除 nums[left];left;}// 3. 统计此时窗口一定满足条件if(条件满足){统计当前窗口;}}数值计算Leetcode 209该题没法使用模板明确2 移除元素的动作和3 统计量就可以了。intminSubArrayLen(inttarget,vectorintnums){intnnums.size();intminLenINT_MAX;intwindowSum0;intleft0;intright0;for(;rightn;right){windowSumnums[right];while(windowSumtarget){//满足条件minLenmin(minLen,right-left1);//更新结果windowSum-nums[left];//更新窗口left;//更新边界}}returnminLenn?minLen:0;}Leetcode 713遵循扩展条件统计的思考方式扩展 product *nums[right];条件当积大于等于k的时候窗口需要收缩统计当积严格小于k的时候统计该次right存在时的满足条件的长度累加起来。intnumSubarrayProductLessThanK(vectorintnums,intk){intnnums.size();longlongproduct1;intleft0;intright0;intres0;for(;rightn;right){product*nums[right];while(productkleftright){product/nums[left];left;}resright-left1;}returnres;}Leetcode 2875Leetcode209的扩展题。一般会考虑两轮就覆盖所有情况于是数组下标采取 % n 取modclassSolution{public:intminSizeSubarray(vectorintnums,inttarget){intnnums.size();intsum0;intleft0;intright0;intresINT_MAX;for(;rightn*2;right){sumnums[right%n];while(leftrightsumtarget){sum-nums[left%n];left;}if(sumtarget)resmin(res,right-left1);}returnresINT_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(vectorintnums,inttarget){//1. 计算总和longlongtotal0;for(intnum:nums)totalnum;//2. 滑动窗口,判断条件全部变为取模intnnums.size();intsum0;intleft0;intright0;intresINT_MAX;for(;rightn*2;right){sumnums[right%n];while(leftrightsumtarget%total){sum-nums[left%n];left;}if(sumtarget%total)resmin(res,right-left1);}//3. 结果记得也加上取模的变化returnresINT_MAX?-1:restarget/total*n;}};Leetcode1004 / 2024Leetcode1004 / 2024 是同一种题目 nums[]只有两种元素的情况下如何使用滑动窗口。

相关新闻