题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
做法:双指针-滑动窗口
什么是滑动窗口?
不断的调节子序列的起始位置和终止位置,进而得出想要的结果。
算法步骤
第一步:right向右移增加窗口,直到窗口内的数字和大于等于S
第二步:记录这个时候的长度,left向右移动,开始减少长度,每减少一次,就更新最小长度,直到窗口内的数小于s
举个栗子
这个时候窗口内所有数字的和只有 2 这个数字,2 小于 7 ,rigth 右移。
这个时候窗口内的数字是 2 3,2 +3 = 5 小于 7 ,rigth 右移
这个时候窗口内的数字是 2 3 1 ,2 +3 +1= 6 小于 7 ,rigth 右移
这个时候窗口内的数字是 2 3 1 2 ,2 +3 +1+2= 8 大于 7 ,记录这个时候的长度 min = 4,left 右移
这个时候窗口内的数字是 3 1 2 ,3 +1+2= 6 小于 7 ,rigth 右移
这个时候窗口内的数字是 3 1 2 4 ,3 +1+2+4= 10 大于 7 , 更新长度 min = 4,left 右移
这个时候窗口内的数字是 1 2 4 ,1+2 +4= 7 等于 7 更新长度 min = 3,left 右移
这个时候窗口内的数字是 2 4 ,2 + 4= 6 小于 7 ,rigth 右移
这个时候窗口内的数字是 2 4 3,2 +4 + 3= 9 大于 7 更新长度 min = 3,left 右移
这个时候窗口内的数字是 4 3,4 + 3= 7 等于 7 更新长度 min = 2,left 右移
这个时候窗口内的数字是 3, 3 小于 7,rigth右移这个循环结束
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums == null || nums.length == 0) return 0;
int left = 0;//左指针
int right = 0;//右指针
int sum = 0;//滑动窗口数值的和
int min = Integer.MAX_VALUE;
//滑动窗口的长度,这里的 Integer.MAX_VALUE;是Integer.MAX_VALUE表示int数据类型的最大取值数:2 147 483 647
while (right < nums.length) {
sum += nums[right];//计算滑动窗口内数字的和
right++;
//每次更新起始位置,并不断比较子序列是否符合条件
while (sum >= s) {
min = Math.min(min, right - left);//取子序列的长度
sum -= nums[left];//这里体现了滑动窗口的精髓之处,不断的变更
left++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
//三元表达式,如果没有符合条件的子序列返回0,否则就是找到了子序列,返回长度
}
}
参考:
https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484315&idx=1&sn=414b885abba34abfd8d9f35c9f61b857&scene=21#wechat_redirect