21-07-08-长度最小的子数组

题目地址

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

题目描述

给定一个含有 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

思路

经典滑动窗口问题，不固定窗口，求满足条件最小

代码

• javascript

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
 var minSubArrayLen = function(target, nums) {
  if (nums.length === 0) return 0;
  let sum = 0;
  let res = 0;
  let left = 0;
  let right = 0;
  // 不断向右移动指针
  while (right < nums.length) {
    sum += nums[right];
    // 当窗口内的连续元素满足条件 (此题中就是和 >= target)
    // 不断迭代收缩左指针，求最小窗口
    while (sum >= target) {
      // 判断是否更新最优解
      // 1. 初始值为0的判断
      // 2. 最优解我们要最小长度，所以用Math.min
      res = res !== 0 ? Math.min(res, right - left + 1) : right - left + 1;
      sum -= nums[left];
      // 收缩左指针，缩小窗口大小
      left ++;
    }
    // 不满足条件，则继续向右走右指针，扩大窗口
    right ++;
  }
  return res;
};

• python3 最近学了一些python，用python也写一下，当作熟悉语法了

class Solution:
  def minSubArrayLen(self, target, nums):
    if (not nums): return 0
    acc = 0
    res = 0
    right = 0
    left = 0
    while (right < len(nums)):
      acc += nums[right]
      while (acc >= target):
        res = min(res, right - left + 1) if res != 0 else right - left + 1
        acc -= nums[left]
        left += 1
      right += 1
    return res

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)