卖萌的弱渣

I am stupid, I am hungry.

Minimum Size Subarray Sum

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

Example

Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

Practice

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution

(Minimum-Size-Subarray-Sum.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        start = 0
        end = 0
        size = len(nums)
        result = size+1
        sum = 0
        while end<size:
            # find the end
            while end<size and sum < s:
                sum += nums[end]
                end += 1
            # find the start
            while start<end and sum >= s:
                result = min(result,end-start)
                sum -= nums[start]
                start += 1
        if result <= size:
            return result
        else:
            return 0