3 Sum Closest | LeetCode

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.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104

Approach:

1. Sort the Array:
   • First, sort the array nums. Sorting helps in efficiently finding the closest sum using the two-pointer technique.
2. Iterate with Two Pointers:
   • Fix one number and use two pointers to find the other two numbers.
     For each element in the sorted array, set two pointers: left at the next element and right at the last element.
   • Calculate the sum of the three elements: current_sum = nums[i] + nums[left] + nums[right].
     Compare the current_sum with the target to check if it’s closer than the previous closest sum.
   • Depending on whether current_sum is less than or greater than the target, move the left pointer rightward (to increase the sum) or the right pointer leftward (to decrease the sum).
   • Continue adjusting the pointers until they converge.
3. Update the Closest Sum: Keep track of the closest sum found during the iteration.
   
4. Return the Closest Sum: After iterating through the array, return the closest sum.

def threeSumClosest(nums, target):
    nums.sort()  # Sort the array
    closest_sum = float('inf')  # Initialize closest_sum to a large number
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            # Update the closest_sum if current_sum is closer to the target
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            
            if current_sum < target:
                left += 1  # Move the left pointer to the right
            elif current_sum > target:
                right -= 1  # Move the right pointer to the left
            else:
                return current_sum  # Return immediately if we find the exact target
    
    return closest_sum

# Example usage:
print(threeSumClosest([-1, 2, 1, -4], 1))  # Output: 2
print(threeSumClosest([0, 0, 0], 1))  # Output: 0

Explanation:

• Time Complexity: O(n^2), where n is the length of the array. This is because the array is sorted first, and then we have two nested loops iterating over the array.
• Space Complexity: O(1), since no extra space is used other than a few variables.