Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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]ands = 7, the subarray[4,3]has the minimal length under the problem constraint.

click to show more practice.

More practice:

If you have figured out theO(n) solution, try coding another solution of which the time complexity isO(nlogn).

题目大意：

给定一个包含n个正整数的数组和一个正整数s，找出其满足和sum ≥ s的子数组的最小长度。如果不存在这样的子数组，返回0

例如，给定数组 [2,3,1,2,4,3]与s = 7， 子数组[4,3]具有满足题设条件的最小长度。

进一步练习： 如果你已经找到了O(n)的解法，尝试使用时间复杂度为O(n log n)的解法完成此题。

解题思路：

O(n)解法：滑动窗口法，使用两个下标left和right标识窗口（子数组）的左右边界。

我们需要定义两个指针left和right，分别记录子数组的左右的边界位置，然后我们让right向右移，直到子数组和大于等于给定值或者right达到数组末尾，此时我们更新最短距离，并且将left像右移一位，然后再sum中减去移去的值，然后重复上面的步骤，直到right到达末尾，且left到达临界位置，即要么到达边界，要么再往右移动，和就会小于给定值.

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        start, end, sum = 0, 0, 0
        bestAns = size + 1
        while end < size:
            while end < size and sum < s:
                sum += nums[end]
                end += 1
            while start < end and sum >= s:
                bestAns = min(bestAns, end - start)
                sum -= nums[start]
                start += 1
        return [0, bestAns][bestAns <= size]

O(nlogn)解法：二分枚举答案，每次判断的时间复杂度为O(n)

二刷：

1. 复杂度：o（n）

2. 小技巧把result设置为len(nums)＋1，用于最后判断结果时，如果没有符合条件的subarray，则result还为len(nums)＋1，最后结果为0

3. 题目中nums中全为正数

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        start, end = 0, 0
        result = len(nums) + 1
        sumValue = 0
        while True:
            if sumValue < s:
                # 终止条件1：end到达末尾，并且如果start减少后，sumvalue小于s的值，则终止
                if end >= len(nums):
                    break
                sumValue += nums[end] 
                end += 1
            else:
                # 终止条件2:在sumvalue大于s的值的情况下，如果start>end，则终止
                if start > end:
                    break
                sumValue -= nums[start]
                start += 1
                result = min(end-start+1, result)
        # 如果nums里面没有符合条件的subarray，那么返回0
        return 0 if result == len(nums) + 1 else result