LeetCode-Solutions/Python/minimum-size-subarray-sum.py at master · tehsints/LeetCode-Solutions · GitHub

History

50 lines (44 loc) · 1.53 KB

Raw

# Time: O(n)

# Space: O(1)

class Solution(object):

# @param {integer} s

# @param {integer[]} nums

# @return {integer}

def minSubArrayLen(self, s, nums):

start = 0

sum = 0

min_size = float("inf")

for i in xrange(len(nums)):

sum += nums[i]

while sum >= s:

min_size = min(min_size, i - start + 1)

sum -= nums[start]

start += 1

return min_size if min_size != float("inf") else 0

# Time: O(nlogn)

# Space: O(n)

# Binary search solution.

class Solution2(object):

# @param {integer} s

# @param {integer[]} nums

# @return {integer}

def minSubArrayLen(self, s, nums):

min_size = float("inf")

sum_from_start = [n for n in nums]

for i in xrange(len(sum_from_start) - 1):

sum_from_start[i + 1] += sum_from_start[i]

for i in xrange(len(sum_from_start)):

end = self.binarySearch(lambda x, y: x <= y, sum_from_start, \

i, len(sum_from_start), \

sum_from_start[i] - nums[i] + s)

if end < len(sum_from_start):

min_size = min(min_size, end - i + 1)

return min_size if min_size != float("inf") else 0

def binarySearch(self, compare, A, start, end, target):

while start < end:

mid = start + (end - start) / 2

if compare(target, A[mid]):

end = mid

else:

start = mid + 1

return start

LeetCode-Solutions/Python/minimum-size-subarray-sum.py at master · tehsints/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

minimum-size-subarray-sum.py

Latest commit

History

Breadcrumbs

minimum-size-subarray-sum.py

File metadata and controls