My Python AC O(n) Solution


  • 1
    R

    The solution has two pointers i and j such that i<j. j increments till the sum of subarray[i:j] is greater than equal to target. Then i increments till the sum is less than the target. The counter for subarray length is maintained.

    def minSubArrayLen(self, s, nums):
            le = len(nums)
            max = le + 1 # maximum length of sub list doesn't be more than the length of the list
            if not nums:
                return 0
            minarray = max
            sum = nums[0]
            i = 0
            j = 1
            while i<j:
                if sum<s and j<le:
                    j = j+1
                    sum = sum + nums[j-1]
                if s<=sum:
                    if minarray>j-i:
                        minarray = j-i
                    sum = sum - nums[i]
                    i = i + 1
                    
                elif j==le:
                    break
            if minarray==max: # if minarray length is unchanged, its sum has always been less than the target
                return 0
            else:
                return minarray

Log in to reply
 

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