Python O(nlgn) binary search for the right most appearance


  • 0
    class Solution(object):
        def minSubArrayLen(self, s, nums):
            sumsofar = [0 for i in xrange(len(nums) + 1)]
            ans = 0xffffffff
            for i in xrange(1, len(nums) + 1):
                sumsofar[i] = sumsofar[i - 1] + nums[i - 1]
                target = sumsofar[i] - s
                left, right = 0, i + 1
                while right - left > 1:
                    mid = (right + left) >> 1
                    if sumsofar[mid] > target:
                        right = mid
                    else:
                        left = mid
                if sumsofar[i] - sumsofar[left] >= s:
                    ans = min(ans, i - left)
            return ans if ans != 0xffffffff else 0      
    

Log in to reply
 

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