209. 长度最小的子数组

Difficulty
Medium
Tags
前缀和
滑动窗口
URL
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
Star
给定一个含有 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)) 时间复杂度的解法。

前缀和 + 滑动窗口

思路
采用滑动窗口来实现。
题解
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, right = 0, 0
        sum_ = 0
        length = float('inf')
        while right < len(nums):
            sum_ += nums[right]
            right += 1
            while sum_ >= target:
                length = min(length, right - left)
                sum_ -= nums[left]
                left += 1

        return length if length != float('inf') else 0
用前缀和的
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = len(nums) + 2
        prefix_sum = [0 for _ in range(0, len(nums)+1)]
        
        for i in range(0, len(nums)):
            prefix_sum[i+1] = prefix_sum[i] + nums[i]

        left, right = 0, 0
        while right < len(prefix_sum)-1:
            right += 1
            while prefix_sum[right] - prefix_sum[left] >= target:
                res = min(res, right-left)
                left += 1

        return res if res <= len(nums) else 0

二分法

思路
涉及到最大最小问题，采用二分法去猜测答案
题解
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, right = 1, len(nums)
        while left <= right:
            mid = left + (right - left) // 2
            if self.isValid(nums, target, mid):
                right = mid - 1
            else:
                left = mid +  1

        return left if left <= len(nums) else 0

    def isValid(self, nums, target, mid):
        sum_ = sum(nums[:mid-1])
        for i in range(mid-1, len(nums)):
            sum_ += nums[i]
            if sum_ >= target:
                return True
            sum_ -= nums[i-mid+1]

        return False