题目

给定一个含有 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. 暴力求解

暴力求解: 18 / 21
思路：双循环

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        # 暴力求解: 18 / 21 
        min_len = float("inf")
        
        for i in range(len(nums)):
            cur_sum = 0
            for j in range(i, len(nums)):
                cur_sum += nums[j]
                if cur_sum >= target:
                    min_len = min(min_len, j -i +1)
                    break
        
        return min_len if min_len != float('inf') else 0

2. 滑动窗口

**思路：**根据滑动窗口算窗口下的总和，如果大于target，则窗口左边+1

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        # 滑动窗口
        l = len(nums)
        left = 0
        right = 0
        sum = 0
        min_lenth = float("inf")

        while right < l:
            sum += nums[right]

            # 当前累计值大于等于target
            while sum >= target:
                min_lenth = min(min_lenth, right - left + 1)
                sum -= nums[left]
                left += 1

            right += 1

        return min_lenth if min_lenth != float("inf") else 0