Share a fast python implementation


  • 1
    Z

    This guy has a fast solution (<150ms)
    http://codesays.com/2014/solution-to-3sum-closest-by-leetcode/

    def threeSumClosest(self, num, target):
        result = 0xFFFFFFFF         # Initially set a impossible large number
        resultDif = 0xFFFFFFFF      # Initially set a impossible large number
    
        num.sort()
    
        i = 0                       # For the first item
        while i < len(num) - 2:
            j = i + 1               # For the middle item
            k = len(num) - 1        # For the last item
            while j < k:
                temp = num[i]+ num[j]+num[k]
                if temp == target:
                    # Not possible to be closer
                    return temp
                elif temp< target:
                    if target - temp < resultDif:
                        # Find a closer combination
                        resultDif = target -temp
                        result = temp
                    # Skip duplicate num[j-1]
                    j += 1
                    while j < k+1 and num[j] == num[j-1]:   j += 1
                else:
                    if temp - target < resultDif:
                        # Find a closer combination
                        resultDif = temp - target
                        result = temp
                    # Skip duplicate num[k+1]
                    k -= 1
                    while k > j-1 and num[k] == num[k+1]:   k -= 1
    
            # Skip duplicate num[i-1]
            i += 1
            while i < len(num)-1 and num[i] == num[i-1]:  i += 1
    
        return result

Log in to reply
 

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