leetcode209 -- 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.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).



class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""

# two pointers

left, right =0,-1

summ = 0

res = len(nums)+1
while left<len(nums):
if right+1<len(nums) and summ<s:   # right is last one
right += 1   # now
summ += nums[right]

else:
summ -= nums[left]
left += 1

if summ>=s:
res = min(res,  right-left+1)

if res==len(nums)+1:
return 0

return res



class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""

# two pointers

left, right =0, 0

summ = 0

res = len(nums)+1
while left<len(nums):
if summ>=s:
res = min(res,  right-left)

if right<len(nums) and summ<s:
summ += nums[right]
right += 1

else:
summ -= nums[left]
left += 1

if res==len(nums)+1:
return 0

return res


class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""

# two pointers

left, right =0, 0

summ = 0

res = len(nums)+1
while left<len(nums):
if summ>=s:
res = min(res,  right-left)

if right<len(nums) and summ<s:
summ += nums[right]
right += 1
elif right ==len(nums) and summ<s:
summ -= nums[left]
left += 1
elif right<len(nums) and summ>=s:
summ -= nums[left]
left += 1
elif right == len(nums) and summ>=s:
summ -= nums[left]
left += 1

if res==len(nums)+1:
return 0

return res



class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""

# two pointers

left, right =0, 0

summ = 0

res = len(nums)+1
while left<len(nums):
if summ>=s:
res = min(res,  right-left)
summ -= nums[left]
left += 1

elif right<len(nums) and summ<s:
summ += nums[right]
right += 1

else:
summ -= nums[left]
left += 1

if res==len(nums)+1:
return 0

return res




class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""

# two pointers

left, right =0, 0

summ = 0

res = len(nums)+1
while left<len(nums):
if summ>=s:
res = min(res,  right-left)

if summ >=s or (summ<s and right==len(nums)):
summ -= nums[left]
left += 1
else:
summ += nums[right]
right += 1

if res==len(nums)+1:
return 0

return res