算法刷题:长度最小的子数组

长度最小的子数组 .题目链接题目详情算法原理滑动窗口定义指针进窗口判断出窗口 我的答案

.

题目链接

长度最小的子数组

题目详情

算法原理 滑动窗口

这道题,我们采用滑动窗口的思想来解决,具体步骤如图所示

定义指针

如图所示,两个指针都需要从左往右进行遍历,因此初始值都为0 除此之外,还需要定义题目所需要的其他变量,如窗口总和sum和窗口总长度len,sum初始值为0,而len的初始值,为了防止比较子数组长度时出错,定义为: Integer.MAX_VALUE

进窗口

sum加上当前right的值,就表示进窗口

判断

此时sum的值小于target,不满足条件,则需要继续进窗口,再次进窗口之前,需要将right往后移动一位 到了这里,终于满足条件了,接下来就进入出窗口的环节了,但是为了解决当前这道题,我们需要在满足条件之后,出窗口之前,更新一下len的最小值

出窗口

所谓的出窗口,就算将sum减去左边left的值,并将left往后移动一位,可以看到,判断当前的sum明显是小于target了,不满足条件,则需要继续进窗口,依次循环,直到right到达数组的边界

我的答案 class Solution { public int minSubArrayLen(int target, int[] nums) { int sum = 0,n = nums.length; //防止比较子数组长度时出错 int len = Integer.MAX_VALUE; //定义指针 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++]; } } //如果没有满足条件的子数组,需要注意返回值 return len==Integer.MAX_VALUE?0:len; } }