Problem Statement in English

You’re given an integer array nums of length n and an integer target. Find three integers in nums such that the sum is closest to target.

Return the sum of the three integers. You may assume that each input would have exactly one solution.

Approach

We can solve this problem using a two-pointer technique. The idea is to sort the array first, and then for each element, use two pointers to find the closest sum of three numbers.

And we’re done!

Solution in Python


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        best = sum(nums[:3])
        n = len(nums)

        for i in range(len(nums)-2):
            if i and nums[i - 1] == nums[i]:
                continue

            l, r = i + 1, len(nums) - 1

            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(target - best) > abs(target - s):
                    best = s

                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                    
                else:
                    return best                   

        return best

Complexity

  • Time: $O(n^2)$
    Since we are using a nested loop to iterate through the array, the time complexity is quadratic in terms of the number of elements in the input array.

  • Space: $O(1)$
    Since we are using a constant amount of space to store variables, the space complexity is constant.

And we are done.