209 長度最小的子數組

1 題目

給定一個含有 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] <= 104

2 解答

1. 利用下一步是否需要收縮為條件

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        n = len(nums)
        left = 0
        ans = inf
        sum = 0

        for right , val in enumerate(nums):
            sum+=val
            while sum - nums[left] >= target:
                sum = sum - nums[left]
                left += 1

            if sum >= target:
                ans = min(ans , right-left+1)

        if ans <=n:
            return ans
        else:
            return 0

2. 利用題目要求$sum \ge target $為條件

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        n = len(nums)
        left = 0
        ans = inf
        sum = 0

        for right , val in enumerate(nums):
            sum+=val

             while sum>=target:
                 ans = min(ans ,  right - left + 1)
                 sum = sum -nums[left]
                 left += 1
                
        if ans <=n:
            return ans
        else:
            return 0