长度最小的子数组

Tips

题目类型: 滑动窗口, 前缀和 + 二分查找

题目

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和大于等于 target 的长度最小的连续子数组, 并返回其长度. 如果不存在符合条件的子数组, 返回 0.

示例

输入: target = 7, nums = [2, 3, 1, 2, 4, 3]

输出: 2

解释: 最小子数组是 [4,3], 因此最小长度是 2

题解

标准的滑动窗口模版.

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let min = Number.MAX_SAFE_INTEGER

  let start = 0
  let end = 0
  let sum = 0
  while (end < nums.length) {
    sum += nums[end++]

    while (sum >= target) {
      min = Math.min(min, end - start)
      sum -= nums[start++]
    }
  }

  return min === Number.MAX_SAFE_INTEGER ? 0 : min
}

时间复杂度: O(n)

题目​

题解​

题目

题解