0209-长度最小的子数组

题目链接

题目描述

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

示例

示例1：

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

提示

• 1 <= target <= 10
• 1 <= nums.length <= 10

• 1 <= nums[i] <= 10

  思路

  思路1：滑动窗口

  维护两个指针 start 和 end 分别表示窗口的起始和结束位置，total 表示窗口内元素和。
  遍历数组，将 nums[end] 加到 total 中，如果 total >= target 则更新长度，然后将 start 右移再重复上述操作，直到 total < target。

  思路2：前缀和+二分查找

  维护数组 sums 表示前缀和，对于其每个元素 sums[i] 找到最小边界 bound 满足 sums[bound] - sums[i] >= target，并更新最小长度。

  题解

  思路1：滑动窗口

  class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = sys.maxsize
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == sys.maxsize else ans

  思路2：前缀和+二分查找

  class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = sys.maxsize
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == sys.maxsize else ans

  复杂度分析

  思路1：滑动窗口

• 时间复杂度：

• 空间复杂度：

  思路2：前缀和+二分查找

• 时间复杂度：

• 空间复杂度：