给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

1
2
3
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

进阶:

  • 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
参考解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
// 双指针
let minLen = nums.length + 1
let i = 0
let j = 0
let sum = 0

while (j < nums.length) { // 放大
sum += nums[j]
while (sum >= s) { // 缩小
sum -= nums[i]
minLen = Math.min(minLen, j - i + 1)
i++
}
j++
}

return minLen === nums.length + 1 ? 0 : minLen
}
参考思路
  • 扩张窗口:为了找到一个可行解,找到了就不再扩张
  • 收缩窗口:在长度上优化该可行解,直到条件被破坏
  • 寻找下一个可行解,然后再优化。