长度最小的子数组-209

[sl1673495]

209.长度最小的子数组

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

示例:

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

进阶:

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

https://leetcode-cn.com/problems/minimum-size-subarray-sum/submissions

思路

暴力法（优化）

纯暴力的循环也就是穷举每种子数组并求和，当然是会超时的，这里就不做讲解了。下面这种解法会在暴力法的基础上稍作优化，具体的思路如下：

1. 先选定下标 i 从 0 作为切分数组的起点，然后下标 j 作为数组的右边界从 0 开始不停向后扩展，每往后一位，就把本次的求和加上新的数字，只要本轮循环的和大于 s，就应该停止循环，因为没必要再往后扩展了，往后扩展的数组长度一定是大于当前长度的。
2. 选定下标 1 为切分数组的起点，进入下一轮循环。

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
let minSubArrayLen = function (s, nums) {
  let min = Infinity
  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      if (sum >= s) {
        min = Math.min(min, j - i + 1)
        if (min === 1) {
          return min
        }
        break
      }
    }
  }
  return min === Infinity ? 0 : min
}

滑动窗口

定义两个下标 i、j 为左右边界，中间的子数组为滑动窗口。在更新窗口的过程中不断的更新窗口之间的值的和 sum。

1. 当 sum < 目标值，说明值不够大，j++，右边界右移。
2. 当 sum >= 目标值，满足条件，把当前窗口的大小和记录的最小值进行对比，更新最小值。并且 i++ 左窗口右移，继续找最优解。

当 i 超出了数组的右边界，循环终止。

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
let minSubArrayLen = function (s, nums) {
  let n = nums.length
  // 定义[i,...j]滑动窗口 取这个窗口里的和
  let i = 0
  let j = -1

  let sum = 0
  let res = Infinity

  while (i < n) {
    if (sum < s) {
      sum += nums[++j]
    } else {
      sum -= nums[i]
      i++
    }

    if (sum >= s) {
      res = Math.min(res, j - i + 1)
    }
  }
  return res === Infinity ? 0 : res
}