3sum, a little optimization


  • 0
    L
    class Solution(object):
        def threeSumSmaller(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if len(nums)<3: return 0
            nums.sort()
            counts=0
            n=len(nums)
            for i in xrange(n-2):
                remains=target-nums[i]
                if remains<nums[i]*2: break
                
                left, right=i+1, n-1
                while(left<right):
                    s=nums[left]+nums[right]
                    if s<remains:
                        counts+=right-left
                        left+=1
                    else:
                        right-=1
            return counts
    

    Consider lower bound is 2nums[i]. So if remains<2nums[i], there is no need to continue


Log in to reply
 

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