滑动窗口
由于数组中的元素全部都是正整数，这意味着当右端点向右移动时，窗口和只会增大；当左端点向右移动时，窗口和只会减小。这个单调性非常适合使用滑动窗口。
用两个指针维护一个区间 $[left, right]$，不断扩大右端点，把当前元素加入窗口和中。一旦窗口和已经大于等于 $target$，就说明当前窗口是一个合法解，此时尝试不断收缩左端点，看看能否在仍然满足条件的前提下把长度变得更短。整个过程中更新最小长度即可。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0, n = nums.length;
int ans = Integer.MAX_VALUE, curSum = 0;
while (right < n) {
curSum += nums[right];
right++;
while (curSum >= target) {
ans = Math.min(ans, right - left);
curSum -= nums[left];
left++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
|