LintCode: Minimum Size Subarray

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 -1 instead.

思路: 本题以two pointer的方法解可得O(N)的solution, 分别用两个pointer代表start和end元素, 当当前的和大于目标时, start向前移动, 当当前的和小于目标时, end向前移动. 时刻更新最小size值. 注意提前处理返回-1的情况.

class Solution:
     # @param nums: a list of integers
     # @param s: an integer
     # @return: an integer representing the minimum size of subarray
    def minimumSize(self, nums, s):
        # write your code here
        if not nums or sum(nums)<s: 
            return -1
        if nums[0] >= s:
            return 1
        else:
            _min = len(nums)
        start, end = 0, 0
        cur = nums[0]
        while end < len(nums):
            if cur < s:
                end += 1
                if end<len(nums):
                    cur+=nums[end]
            else:
                if end-start+1<_min:
                    _min = end-start+1
                start+=1
                cur-=nums[start-1]
        return _min