# Solution For 3sum Closest

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

## Step by Step Implementation For 3sum Closest

```class Solution {
public int threeSumClosest(int[] nums, int target) {
// sort the array first
Arrays.sort(nums);
int closestSum = nums + nums + nums;
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
// update closestSum if the current sum is closer to target
if (Math.abs(target - sum) < Math.abs(target - closestSum)) {
closestSum = sum;
}
// move left or right pointer based on current sum
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
// we found an exact match, no need to continue
return sum;
}
}
}
return closestSum;
}
}```
```class Solution:
def threeSumClosest(self, nums, target):
# Sort the array
nums.sort()
# Set the closest variable to the max value of an integer
closest = 2147483647
# Iterate through the array
for i in range(len(nums) - 2):
# Set left pointer to i + 1
left = i + 1
# Set right pointer to the end of the array
right = len(nums) - 1
# While the left pointer is less than the right pointer
while left < right:
# Set the sum to be the values of nums at indices i, left, and right
sum = nums[i] + nums[left] + nums[right]
# If the sum is equal to the target
if sum == target:
# Return the sum
return sum
# If the sum is less than the target
if sum < target:
# If the sum is closer to the target than the current value of closest
if target - sum < abs(target - closest):
# Set closest equal to the sum
closest = sum
# Increment the left pointer
left += 1
# If the sum is greater than the target
else:
# If the sum is closer to the target than the current value of closest
if sum - target < abs(target - closest):
# Set closest equal to the sum
closest = sum
# Decrement the right pointer
right -= 1
# Return the closest value
return closest```
```var threeSumClosest = function(nums, target) {
// sort the array
nums.sort((a, b) => a - b);
// initialize the closest value to be the first sum in the array
let closest = nums + nums + nums;
// iterate through the array
for (let i = 0; i < nums.length - 2; i++) {
// initialize left pointer at i + 1
let left = i + 1;
// initialize right pointer at end of array
let right = nums.length - 1;
// while the left pointer is less than the right pointer
while (left < right) {
// calculate the sum
let sum = nums[i] + nums[left] + nums[right];
// if the sum is equal to the target, return the sum
if (sum === target) {
return sum;
// if the sum is less than the target, move the left pointer up one
} else if (sum < target) {
left++;
// if the sum is greater than the target, move the right pointer down one
} else {
right--;
}
// if the absolute value of the sum minus the target is less than the absolute value of the closest value minus the target
if (Math.abs(sum - target) < Math.abs(closest - target)) {
// set the closest value to the sum
closest = sum;
}
}
}
// return the closest value
return closest;
};```
```class Solution {
public:
int threeSumClosest(vector& nums, int target) {
int result = nums + nums + nums;
int min_diff = abs(result - target);
// sort the array
sort(nums.begin(), nums.end());
// fix the smallest number as nums[i]
for (int i = 0; i < nums.size() - 2; i++) {
// start from i + 1
int left = i + 1;
// end at nums.size() - 1
int right = nums.size() - 1;
// until left meets right
while (left < right) {
// calculate the sum
int sum = nums[i] + nums[left] + nums[right];
// update the result if it's closer to the target
if (abs(sum - target) < min_diff) {
result = sum;
min_diff = abs(sum - target);
}
// if the sum is too small, move left
if (sum < target) {
left++;
}
// if the sum is too large, move right
else {
right--;
}
}
}
return result;
}
};```
```public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
Array.Sort(nums);
int closestSum = nums + nums + nums;
for (int i = 0; i < nums.Length - 2; i++)
{
int left = i + 1;
int right = nums.Length - 1;
while (left < right)
{
int sum = nums[i] + nums[left] + nums[right];
if (sum == target)
{
//We found an exact match, return the sum
return sum;
}
else if (sum < target)
{
//The sum is too low, increment the left pointer
left++;
}
else
{
//The sum is too high, decrement the right pointer
right--;
}
//Update closestSum if the current sum is closer to the target
if (Math.Abs(sum - target) < Math.Abs(closestSum - target))
{
closestSum = sum;
}
}
}
return closestSum;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]