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)
            
    

  • 1
      def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) < 3: return
        sub_closest_dist = sys.maxint
        closest = 0
        nums.sort()
        for i in range(len(nums)-2):
          l = i + 1; r = len(nums) - 1
          sub_target = target - nums[i]
          while l < r:
            s = nums[l] + nums[r]
            if abs(s - sub_target) < sub_closest_dist:
              sub_closest_dist = abs(s - sub_target)
              closest = s + nums[i]
            if s > sub_target:
              r -= 1
            else:
              l += 1
        return closest
    

    This one has better readability:

      def threeSumClosest(self, nums, target):
        if len(nums) < 3: return
        nums.sort()
        result = nums[0] + nums[1] + nums[2]
        for i in range(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(s - target) < abs(result - target):
              result = s
            if s < target:
              l += 1
            elif s > target:
              r -= 1
        return result
    

Log in to reply
 

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