“滑动窗口”算法专项训练

算法专项训练"/>

“滑动窗口”算法专项训练

目录

题目链接：长度最小的子数组

题目描述

思路分析：滑动窗口(利用单调性，使用"同向双指针'来优化)

细节处理

画图解析

代码

题目链接：最大连续1的个数 III

题目描述

思路分析：滑动窗口(同向双指针)

细节处理

画图解析

代码

题目链接：将 x 减到 0 的最小操作数

题目描述

思路分析： 滑动窗口(同向双指针)

细节处理

画图解析

代码

---

题目链接：长度最小的子数组

题目描述

思路分析：滑动窗口(利用单调性，使用"同向双指针'来优化)

1. 定义左右指针left和right
2. right指针进入窗口
3. while（判断是否满足窗口内部和的值大于等于目标值的条件
4. 更新最小长度以及窗口和的值
5. left出窗口 ）

细节处理

• 单调性规避了很多没必要的枚举行为，因为在找到满足条件的窗口和之后，right指针继续进入窗口的长度肯定比原来的大，所以找到满足条件的窗口和之后应该出窗口
• 同向双指针指的是left和right都是往一个方向移动，不会回退 

画图解析

代码

public int minSubArrayLen(int target,int[]nums) {int n= nums.length,len=Integer.MAX_VALUE,sum=0;for (int left = 0,right=0; right < n; right++) {//进窗口sum+=nums[right];while (sum>=target){//判断len=Math.min(len,right-left+1);sum-=nums[left];left++;//出窗口}}return len==Integer.MAX_VALUE?0:len;}

题目链接：最大连续1的个数 III

题目描述

 

思路分析：滑动窗口(同向双指针)

1. 定义左右指针left和right以及统计0的个数zero
2. right指针进入窗口
3. while（判断是否满足窗口内部zero的值大于等于最多反转个数k的条件
4. left出窗口)
5. 更新最长长度

细节处理

在找到超过反转个数的right位置时，left不用走一步就更新一次，因为在刚找到的那个位置的长度一定比left往后面一步一步走的长度长（例1比例2长）

画图解析

代码

public int longestOnes(int[] nums, int k) {int n=nums.length,zero=0,len=0;for (int right = 0,left=0; right < n; right++) {if(nums[right]==0) zero++;//进窗口while (zero>k){//判断if(nums[left]==0) zero--;//出窗口left++;}len=Math.max(len,right-left+1);}return len;}

题目链接：将 x 减到 0 的最小操作数

题目描述

思路分析： 滑动窗口(同向双指针)

1. 定义左右指针left，right和数组总和sum，窗口长度len=-1
2. right进入窗口得到temp
3. whlie（判断sum是否大于temp
4. 是的话left出窗口）
5. 如果sum==target则更新结果长度len，取最大
6. 用数组总长度-窗口满足条件的最大长度即得到结果

 

细节处理

• 巧妙转化：遇难则反，将问题转化为求数组总和减去目标数的窗口的最长长度，数组总长度减去最长长度即可得到最小操作数。
• 当right走到sum>=target位置时，left++,right不用回退left再走一遍，因为right还是要走到当前位置才满足条件。left需要走是因为如果sum>target，那left出窗口可能会找到sum==target

画图解析

代码

 public int minOperations(int[] nums, int x) {int sum=0;int n=nums.length;int len=-1;for (int i : nums) sum+=i;int target=sum-x;
//        如果x的值大于所有数之和，直接返回-1if(target<0) return -1;for (int right = 0,left=0,temp=0; right < n ; right++) {temp+=nums[right];//进窗口while (temp>target){//判断temp-=nums[left];left++;//出窗口}if(temp==target){len=Math.max(len,right-left+1);//更新结果}}if(len==-1)  return len;else return n-len;}