leetcode209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

思路:思路其实很简单，就是维护一个动态的滑动窗口，我感觉大家都会这么想吧。看了题解后，发现似乎官方都不是一开始用的滑动窗口！我们可以通过一个窗口来维持里面的数的和始终小于target,不断往里面增加数字，大于等于target时，就需要移动左边的指针，不断缩减，因为我们的目标是求得最短的，所以要是的窗口的区间足够小。

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n=len(nums)
        l=0
        res=float("inf")
        tmp=0
        for r in range(n):
            tmp+=nums[r]
            while(tmp>=s):
                res=min(res,r-l+1)
                tmp-=nums[l]
                l+=1
        return res if(res!=float("inf")) else 0

原文地址：https://blog.csdn.net/weixin_44245188/article/details/143431715

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！