Skip to content

Latest commit

 

History

History
54 lines (42 loc) · 1.28 KB

0209-长度最小的子数组.md

File metadata and controls

54 lines (42 loc) · 1.28 KB

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

 

示例 1:

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

输入:target = 4, nums = [1,4,4] 输出:1 示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0  

提示:

1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105  

进阶:

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

var minSubArrayLen = function(target, nums) {
  const len = nums.length
  let min = Number.MAX_VALUE
  if (len === 0) {
    return 0
  }
  let start = 0, end = 0
  let sum = 0
  while(end < len) {
    sum += nums[end]
    while(sum >= target) {
      min = Math.min(min, end - start + 1)
      sum -= nums[start++]
    }
    end++
  }
  return min === Number.MAX_VALUE ? 0 : min
};

解题思路: 滑动窗口,遇到总和大于等于目标值的时候就记录下来并清除左边的值直到小于目标值,然后继续增加下面的值