209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

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

My idea:双指针，一个记录，一个重置备用，结果超时了/微笑，也是，我这时间复杂度也太高了。。。

class Solution:
    def minSubArrayLen(self, s, nums):
        su=0
        count=0
        end=len(nums)
        a=0
        b=1
        c=2
        if(sum(nums)<s):
            return 0
        for i in nums:
            if (su < s):
                su += i
                count = count + 1
            else:
                break 
        a=count
        su=0
        count=0

        while(c<end):
            while ((su < s)&(b<end)):
                su += nums[b]
                count = count + 1
                b=b+1

            if((a>count)&(su>=s)):
                a=count
            b=c
            c=c+1
            su=0
            count=0

        return a

只能借鉴别人的咯

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        k,res,sum_i = -1,n+1,0
        for i in range(n):
            sum_i += nums[i]
            if sum_i >= s:
                while sum_i-nums[k+1] >= s:
                    sum_i -= nums[k+1]
                    k += 1
                res = min(res,i-k)
        if res == n+1:
            return 0
        else:
            return res

前后指针，滑动窗口

这种题目还是得自己思考琢磨比较好，别想着遍历一股脑暴力解

209. Minimum Size Subarray Sum

相关推荐