Technical Interview Question

You are given an array nums of n integers, and a target value target. Your task is to find three integers in nums such that the sum is closest to target. Return the sum of those three integers.

Example

nums = [-1, 2, 1, -4]
target = 1

threeSumClosest(nums, target) => 2

Explanation:
The sum that is closest to the target (1) is (-1 + 2 + 1 = 2).

Constraints

• The length of the input array is at least 3.
• -10^3 <= nums[i] <= 10^3 for all 0 <= i < n.
• -10^4 <= target <= 10^4.

Answer

To solve this problem, we can use a two-pointer approach along with sorting the array.

1. Sort the input array nums in ascending order.
2. Initialize a variable closestSum to store the sum of the three closest integers.
3. Iterate through the array from left to right using a variable i: 4. Set left pointer left to i + 1 and right pointer right to n - 1. 5. While left < right: 6. Calculate the sum of the three integers at indices i, left, and right: sum = nums[i] + nums[left] + nums[right]. 7. If the absolute difference between sum and target is less than the absolute difference between closestSum and target, update closestSum to sum. 8. If sum is less than target, increment left by 1. 9. If sum is greater than target, decrement right by 1. 10. If sum is equal to target, return target as the closest sum.
4. Return closestSum as the closest sum to the target.

Here is the implementation of the threeSumClosest function in Python:

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closestSum = float('inf')
    
    for i in range(n-2):
        left = i + 1
        right = n - 1
        
        while left < right:
            currSum = nums[i] + nums[left] + nums[right]
            
            if abs(currSum - target) < abs(closestSum - target):
                closestSum = currSum
            
            if currSum < target:
                left += 1
            elif currSum > target:
                right -= 1
            else:
                return target
                
    return closestSum

The time complexity of this solution is O(n^2) since for each element in the array, we iterate through the remaining portion using two pointers.