给定一个含有 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
}
参考思路
  • 扩张窗口：为了找到一个可行解，找到了就不再扩张
  • 收缩窗口：在长度上优化该可行解，直到条件被破坏
  • 寻找下一个可行解，然后再优化。