问题
给定一个含有 \(n\) 个正整数的数组和一个正整数 \(s \),找出该数组中满足其和 \(≥ s \)的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回\( 0\)。
示例:
输入: \(s = 7, nums = [2,3,1,2,4,3]\)
输出: \(2\)
解释: 子数组 \([4,3]\) 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了\(O(n)\) 时间复杂度的解法, 请尝试\( O(n log n)\) 时间复杂度的解法。
解法
连续子数组,考虑使用双指针\(start\)与\(end\)滑动窗口来判断.设置一个\(sum\)值,表示滑动窗口中的和,每一轮循环,判断\(sum\)与\(s\)的关系,有两种情况:
- \(sum\)大于等于\(s\),此时\(sum\)减去\(start\)指针所指向的值,\(start\)指针前进。
- \(sum\)小于\(s\),此时,\(sum\)加上\(end\)的值,\(end\)指针前进。
代码
java实现
class Solution {
public int minSubArrayLen(int s, int[] nums) {
// 注意这里的end的起始位置
int start = 0, end = -1;
int result = Integer.MAX_VALUE, sum = 0;
// 开始循环,循环跳出的条件是start指针循环到数组尾部了
while (start < nums.length) {
// 这里需要注意判断条件
if (sum < s && end + < nums.length) {
end++;
sum += nums[end];
} else {
sum -= nums[start];
start++;
}
if (sum >= s) result = result < end - start + 1 ? result : end - start + 1;
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}