3Sum Closest


  • 0
    D
    class Solution:
        """
        the basic idea is 1, sort the input list
        2. change the problem to twoSumCloset
        """
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            numbers = nums
            
            if len(numbers) < 3:
                return
            
            numbers.sort() # very important for latter action
            
            result = sys.maxsize
            minDiff = sys.maxsize
            
            #loop the sorted numbers
            for idx, num in enumerate(numbers):
                t = target - num
                #go to twoSum problem
                curDiff, twoSumResults = self.twoSumCloset(numbers[idx+1:], t)
                if minDiff > curDiff:
                    minDiff = curDiff
                    result = num + numbers[idx+1+twoSumResults[0]] + numbers[idx+1+twoSumResults[1]]
        
            return result
    
        
        def twoSumCloset(self, numbers, target):
            idx1 = None
            idx2 = None
            
            minDiff = sys.maxsize
            start, end =0, len(numbers)-1
            
            # loop: change the sum by moving from the left(+1) or right(-1)
            # make use of the sorted numbers
            while start < end:
                curSum = numbers[start] + numbers[end]
                curDiff = abs(curSum-target)
                if curDiff < minDiff:
                    minDiff = curDiff
                    idx1 = start
                    idx2 = end
                    
                if curSum < target:
                    start += 1
                elif curSum > target:
                    end -=1
                else: # it means curSum=target!!!
                    break
                    
            return minDiff, [idx1, idx2]
    

Log in to reply
 

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