Python O(N^2) solution


  • 30
    G
    class Solution:
        # @return an integer
        def threeSumClosest(self, num, target):
            num.sort()
            result = num[0] + num[1] + num[2]
            for i in range(len(num) - 2):
                j, k = i+1, len(num) - 1
                while j < k:
                    sum = num[i] + num[j] + num[k]
                    if sum == target:
                        return sum
                    
                    if abs(sum - target) < abs(result - target):
                        result = sum
                    
                    if sum < target:
                        j += 1
                    elif sum > target:
                        k -= 1
                
            return result

  • 0
    S
    This post is deleted!

  • 0
    S

    What if you put the

    if sum == target:
    return sum
    at the end of the checks so the if code only runs when the outcome is true?


  • 1
    R

    Similar idea in Python, based on 3Sum code:

    class Solution(object):
        def threeSumClosest(self, nums, target):
            res = []
            nums.sort()
            closestDiff = sys.maxint
            sign = 1
            for i in xrange(len(nums)-2):
                l, r = i+1, len(nums)-1
                
                while l < r:
                    s = nums[i] + nums[l] + nums[r]
                    if s == target:
                        return s
                    if abs(target - s) < closestDiff:
                        sign = -1 if target - s < 0 else 1
                    closestDiff = min(abs(target - s), closestDiff)
                    if s < target:
                        l +=1 
                    elif s > target:
                        r -= 1
            return target - (closestDiff * sign)
            
    

Log in to reply
 

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