Python O(n^2), highly optimized, beats 95%


  • 1

    Similar to 3sum but we track the closest value instead:

    - Yangshun

    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            # Time: O(n^2)
            # Space: O(lgn)
            nums, length, closest = sorted(nums), len(nums), float('inf')
            for i in range(length - 2):
                # Previous value of i has been accounted for.
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                j, k = i + 1, length - 1
                while j < k:
                    total = nums[i] + nums[j] + nums[k]
                    if abs(total - target) < abs(closest - target):
                        closest = total
                    # Total exceeds target, decrement k so that total sum becomes smaller
                    if total > target:
                        # Find the next different k.
                        while j < k and nums[k] == nums[k - 1]:
                            k -= 1
                        k -= 1
                    else:
                        if total == target:
                            return target
                        # Find the next different j.
                        while j < k and nums[j] == nums[j + 1]:
                            j += 1
                        j += 1
            return closest
    

Log in to reply
 

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