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.

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

解题方法

首先要问清楚面试官，如果没有解应该返回什么，比如

• [1,1], 3
• [], 2 ....

two pointer

这道题可以用two pointer解，对每一个i,将j向右移，直到sum >= s, 后面的j就不用看了，因为都是positive,所以肯定大于s

time complexity: O(n) space complexity: O(1)

二分法

这种subarray sum的题目，很多都可以采取类似的方法： 用一个sums[]， sums[i]表示nums[0:i]的sum，然后对于sums[i], 用二分法找到右边的边界，因为都是Positive number，所以sums必然是一个 递增sorted array.

Solution

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return 0
        p1, p2 = 0, 0
        currSum = 0
        minLen = sys.maxint
        while p1 < length:
            while currSum < s and p2 < length:
                currSum += nums[p2]
                p2 += 1
            #if currSum is larger than s, count the len
            #in case of the p2 >= length
            if currSum >= s:
                currLen = p2 - p1
                if minLen > currLen:
                    minLen = currLen
            currSum -= nums[p1]
            p1 += 1

        if minLen == sys.maxint:
            return 0
        else:
            return minLen

二分法

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return 0
        sums = [0 for i in range(length+1)]
        result = sys.maxint
        sums[1] = nums[0]
        for i in range(1, length+1):
            sums[i] = sums[i-1] + nums[i-1]

        for i in range(length):
            rightEnd = self.searchRight(i, length, sums[i] + s, sums)
            if rightEnd != length + 1:
                currLen = rightEnd - i
                if currLen < result:
                    result = currLen

        if result == sys.maxint:
            return 0
        else:
            return result

    def searchRight(self, start, end, target, sums):
        while start + 1 < end:
            mid = start + (end - start) / 2
            if sums[mid] >= target:
                end = mid
            else:
                start = mid
        if sums[start] >= target:
            return start
        if sums[end] >= target:
            return end
        return len(sums) + 1