3sum Closest - Leetcode Solution

Problem Description:

Given an array nums of n integers 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:

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).

Solution:

To solve this problem, we can use the two-pointer approach. First, we sort the given input array. This allows us to easily traverse through all the possible values of the three numbers. We then fix the first number and move the second and third numbers such that we calculate their sum and check if it is closest to the target. We then update the closest sum so far and move the second and third numbers accordingly. We keep doing this until we have checked all possible combinations of the three numbers.

Algorithm:

1. Sort the given input array nums.
2. Initialize a variable res to store the closest sum so far. Set it to a large number initially.
3. Traverse through the array nums from left to right. Fix the first number as the i-th number.
4. Initialize two pointers, left and right. Set left to i+1 and right to n-1.
5. While left < right, calculate the sum of the three numbers, i.e., nums[i] + nums[left] + nums[right].
6. If the sum is equal to target, return the sum.
7. If the sum is less than target, increment left.
8. If the sum is greater than target, decrement right.
9. Check if the absolute difference between the sum and target is less than the absolute difference between res and target.
10. If yes, update res with the new sum.
11. Repeat steps 5-10 until all possible combinations of the three numbers have been checked.
12. Return res.

Implementation:

Here is the Python code to implement the above algorithm:

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

Time Complexity:

The time complexity of the above algorithm is O(n^2), where n is the length of the input array. This is because we traverse through the array twice, once to sort the array, and then to find the closest sum. Within the second traversal, we use a two-pointer approach, which takes O(n) time.

Space Complexity:

The space complexity of the above algorithm is O(1), as we are not using any extra space. We are only using a few variables to store the closest sum, pointers, and the input array.

1