LeetCode 209. 长度最小的子数组
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
LeetCode 题目209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target = 7, nums = [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。
解析滑动窗口解法使用双指针来解该算法题。
初始化定义参数两个指针分别是slowfast初始都为0。sum连续子数组值的和初始值为0。min最小连续子数组的长度也是最终的返回值初始值设置为Integer.MAX_VALE。
int min = Integer.MAX_VALUE,slow = 0,sum=0;
- 在第一层for循环中使sum+= fast指针指向的值。
sum+=nums[fast];
- 第二步进行判断假如累加之后的sum值>target目标值则进入while循环
- 在while循环中先判断当前子序列长度是否为最短子序列假如是就将当前子序列值赋值给min。
min = Math.min(min,fast-slow+1);
- 依次递减slow指针对应数组中的值并移动slow指针位置。while循环跳出条件为sum<target。
sum-= nums[slow++];
- 循环完毕返回min值。
完整代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE,slow = 0,sum=0;
for(int fast=0;fast<nums.length;fast++) {
sum+=nums[fast];
while(sum>=target) {
min = Math.min(min,fast-slow+1);
sum-= nums[slow++];
}
}
return min==Integer.MAX_VALUE?0:min;
}
}