Minimum Size Subarray Sum

Similar Problems:

- Subarray Product Less Than K
- Two Sum
- CheatSheet: Leetcode For Code Interview
- Tag: #manydetails, #twopointer, #maxsubarraysum

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] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

More practice:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/minimum-size-subarray-sum ## Basic Ideas: Two pointers + Ge accumulated sum ## ## Corner case: 0 elements or 1 elements ## Right pointer move one step each time. ## Left pointer don't need to move left. Why? We only need to find the minimal length ## ## Complexity: Time O(n), Space O(1) import sys class Solution: def minSubArrayLen(self, s, nums): """ :type s: int :type nums: List[int] :rtype: int """ length = len(nums) if length == 0: return 0 min_length = sys.maxsize left, sum_v = 0, 0 # always move right by 1 step for right in range(0, length): sum_v += nums[right] while sum_v >=s: min_length = min(min_length, right-left+1) # left won't pass right. Why? Because s>0 sum_v -= nums[left] left += 1 return min_length if min_length != sys.maxsize else 0