209. Minimum Size Subarray Sum

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

solution

• 暴力法: 超时

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:  
        res = len(nums) + 1

        for i in range(len(nums)):
            for j in range(i+1, len(nums)+1):  # 左闭右开
                seq_sum = sum(nums[i:j])
                if seq_sum >= target:
                    res = min(res, j - i)

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

时间复杂度：O() 空间复杂度：O()

• 滑动窗口一个for+一个while写法

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = 0
        sub_sum = 0
        res = float('inf')

        for r in range(len(nums)):       
            sub_sum += nums[r]

            while sub_sum >= target:
                res = min(res, r - l + 1)
                sub_sum -= nums[l]
                l += 1    
                            
        return res if res != float('inf') else 0

• 滑动窗口

  • 窗口内是什么？如何移动窗口的起始位置？如何移动窗口的结束位置？

# 左闭右闭，本质上只有一次循环，时间复杂度为O(1)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = float('inf')
        l = 0
        r = 0
        sum_lr = nums[0]

        while l <= r and r < len(nums):
            if sum_lr < target:
                r += 1
                if r <= len(nums) - 1:
                    sum_lr += nums[r]
            else:
                res = min(res, r - l +1)
                sum_lr -= nums[l]
                l += 1
        return res if res != float('inf') else 0

时间复杂度：O(n) 空间复杂度：O(1)

follow up

如果数组中有正有负该如何解决?看到连续子序列的和可以考虑前缀和

560. Subarray Sum Equals K