Minimum Size Subarray Sum

Question

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.

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.

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

Thoughts

如果发现了一个[i,j], sum >= s, 那么之后的[i, j+1], [i, j+2]....都不用看了 保持j的位置，减去i的元素直到找到一个新的符合条件的subarray

Solution

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
        i = 0
        j = 0
        sum = 0
        ans = sys.maxint
        for i in range(len(nums)):
            while j < len(nums) and sum < s:
                sum += nums[j]
                j += 1
            if sum >= s:
                ans = min(j-i, ans)
            sum -= nums[i]

        if ans == sys.maxint:
            return -1
        else:
            return ans