题目描述

 给定一个含有 n 个正整数的数组和一个正整数 target 。

 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

原题请参考链接https://leetcode-cn.com/problems/minimum-size-subarray-sum/

题解

方法一 【暴力破解】

# 此方法会存在超时，在这里只是作为一种方法提供
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        l = len(nums)
        ans = l + 1
        for i in range(l):
            total = 0
            for j in range(i,l):
                total += nums[j]
                if total >= target:
                    ans = min(ans,j-i+1)
                    break
        return 0 if ans==l+1 else ans

方法二 【双指针(滑动窗口)】

# 如用滑动窗口实现，必须确定如下三点：
# 1.窗口内是什么
# 2.如何移动窗口的起始位置
# 3.如何移动窗口的结束位置
# 解答
# 1.窗口就是 满足其和 ≥ s的长度最小的连续子数组。
# 2.窗口的起始位置为数组的起始位置，如果当前窗口的值大于s，窗口就要向前移动，等价于缩小窗口的值
# 3.窗口的结束位置为数组的最大长度-1，如果当前窗口的值小于s，窗口就要向前移动，等回家与扩大窗口的值
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        l = len(nums)
        total = 0
        ans = l + 1
        start,end = 0,0
        while end < l:
            total += nums[end]
            while total >= target:
                ans = min(end-start+1,ans)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans==l+1 else ans