# Python O(n) and O(n log n) solution

• ``````class Solution:

def minSubArrayLen(self, s, nums):
total = left = 0
result = len(nums) + 1
for right, n in enumerate(nums):
total += n
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return result if result <= len(nums) else 0
``````

O(n log n)

``````class Solution:

def minSubArrayLen(self, target, nums):
result = len(nums) + 1
for idx, n in enumerate(nums[1:], 1):
nums[idx] = nums[idx - 1] + n
left = 0
for right, n in enumerate(nums):
if n >= target:
left = self.find_left(left, right, nums, target, n)
result = min(result, right - left + 1)
return result if result <= len(nums) else 0

def find_left(self, left, right, nums, target, n):
while left < right:
mid = (left + right) // 2
if n - nums[mid] >= target:
left = mid + 1
else:
right = mid
return left``````

• The worst case of the nested loop is O(n^2) in the first solution, isn't it?

• no, it's not. cuz in total we only do O(n) subtractions. (we do subtraction to make length shorter, and the max length is n.)

• @liji94188
How about [1,1,1,1,1,1,1,100] and want 8

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.