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

目录

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

题目描述

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

细节处理

画图解析

代码

题目链接：最大连续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的值大于所有数之和，直接返回-1
        if(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;
    }