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.

For 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.

解题方法

2-pointer基本题

Solution

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        min_length = sys.maxint
        cur_sum = 0
        p_1 = 0
        p_2 = 0

        while p_1 < length:
            while p_2 < length and cur_sum < s:
                cur_sum += nums[p_2]
                p_2 += 1
            if cur_sum >= s:
                min_length = min(min_length, p_2-p_1)
            cur_sum -= nums[p_1]
            p_1 += 1
        if min_length == sys.maxint:
            return 0
        else:
            return min_length

Reference