Minimum Size Subarray Sum

比较简单的双指针，没有什么陷阱可言

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        cur = 0
        cumSum = 0
        result = sys.maxint

        for i in xrange(n):
            while cur < n and cumSum < s:
                cumSum += nums[cur]
                cur += 1

            if cumSum >= s:
                result = min(result, cur - i)
                cumSum -= nums[i]
            else:
                break

        return result if result != sys.maxint else 0

此题还有O(nlgn)的二分法解答，暂时没看

二分法的方法实际就是二分数量，因为我们要求的就是最小数量，所以算作是二分答案也可以，对于检查函数实际上我们做的还是在用双指针

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        start, end = 0, len(nums)
        while start + 1 < end:
            mid = start + (end - start) / 2
            if self.check(nums, mid, s):
                end = mid
            else:
                start = mid

        if self.check(nums, start, s):
            return start
        return end if self.check(nums, end, s) else 0

    def check(self, nums, count, target):
        n = len(nums)
        cum = sum(nums[:count])

        for i in xrange(n - count + 1):
            if cum >= target:
                return True
            if i < n - count:
                cum -= nums[i]
                cum += nums[i + count]
        return False