求解思路
这道题我们维护一个窗口,右边界不断向右扩展把新元素加进来累加和,当窗口内的和已经达标时,就尝试收缩左边界来找更短的满足条件的子数组。
具体来说就是,右指针每次向右移动一位把新数加到sum里,然后进入一个while循环去判断:
如果把左边界的数移出窗口后sum仍然能达到target,那就果断移出去让窗口变小,这样反复收缩左边界直到不能再缩为止,此时的窗口就是以当前右边界结尾的最短达标子数组。
每次右指针移动后都检查当前窗口是否达标,如果达标就用窗口长度更新答案的最小值。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static int minSubArrayLen(int target, int[] nums) {
int ans = Integer.MAX_VALUE;
for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
sum += nums[r];
while (sum - nums[l] >= target) {
// sum : nums[l....r]
// 如果l位置的数从窗口出去,还能继续达标,那就出去
sum -= nums[l++];
}
if (sum >= target) {
ans = Math.min(ans, r - l + 1);
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~