Python O(n) Solution


  • 1
    S

    Trick here is to keep adding numbers from the start of array until you hit the target. After that we keep adding numbers from the end and subtracting numbers from the start as long as the total is still above target and checking if the new array is the minimum length. The intuition is that for example, a 10 added on the end could replace two 5's from start of array and thus the reduce the number of elements needed to hit target in that subarray.

    class Solution(object):
        def minSubArrayLen(self, s, nums):
            minLen, total, start = len(nums) + 1, 0, 0
            for i in range(len(nums)):
                total += nums[i]
                while total >=  s:
                    minLen, total, start = min(i - start + 1, minLen), total - nums[start], start + 1
            return 0 if minLen > len(nums) else minLen

Log in to reply
 

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