长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
1 2 3
| 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
|
思路: 先遍历找到第一个累加到大于等于target的索引值idx,找不到就返回0. 随后设置左指针为0, 右指针为idx. 通过控制左右指针移动寻找最短连续子数组长度
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| class Solution { public int minSubArrayLen(int target, int[] nums) { int match = nums.length; int sum = 0; int beginIdx = -1; for(int i = 0; i < nums.length; i++) { sum += nums[i]; if(sum >= target) { beginIdx = i; break; } } if(beginIdx == -1) { return 0; } int l = 0; int r = beginIdx; while(l <= r && r < nums.length) { if(sum >= target) { match = Math.min(match, r - l + 1); if(match == 1) { return 1; } sum -= nums[l]; l++; } else { r++; if(r >= nums.length){ break; } sum += nums[r]; } } return match; } }
|