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


  • 11
    T
    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

  • 0
    C

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


  • 1
    L

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


  • 0
    Y

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


  • 0
    C
    This post is deleted!

Log in to reply
 

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