Input: [-1, 2, 1, -4]
Key = 1Output:
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)This problem is also known as three sum closest The solution to this problem is similar to “two sums”. Hence I would recommend you to please check out the solution to that problem before proceeding to this.
Below are the steps that we can arrive at the solution.
Step 1: Sort the array.
Step 2: Take an initial integer “closest_sum” that stores the value of first 3 numbers from the array.
closest_sum = arr[0] + arr[1] + arr[2]
This variable stores the final result.
Step 3: Take a for loop, that starts from starting of the array.
Now we have to find 2 integers whose sum is closest to the key value.
Hence this problem is similar to two sum problem.
Now we take 2 pointers, left pointer starting from beginning of the array, then the right pointer from the end of the array.
Then we add those elements present in the index, if the sum is less than the current “closest_sum”, then we have to update with the new value.
The above step 3 can be programmatically written as below:
for (int i = 0 to array_length -1 )
{
left_pointer = i + 1;
right_pointer = array_length - 1;
while (left_pointer < right_pointer)
{
sum = nums[i] + nums[left_pointer] + nums[right_pointer];
if (abs(sum - target) < abs(closetSum - target)) // to find the closest sum we use this formula
{
closetSum = sum; // update the closest sum
}
if (sum < target)
{
insrement left_pointer
}
else
{
decrement right_pointer
}
}
} Let us understand with the help of an example.
We take a sorted array [-4, -1, 1, 2] and key = 1
closest_sum =. -4 -1 + 1 = -4
Pass 1 of for loop:
i = 0
left_pointer = 1
Right_pointer = 3
Pass 1 of while loop
1 < 3
sum = -4 -1 +2 = -3
if (4 < 5)
closest_sum = -3
if (-3 < 1)
true
increment left_pointer
Pass 2 of while loop
2 < 3
sum = -4 + 1 +2 = -1
if (2 < 4)
closest_sum = -1
if (-1 < 2)
true
increment left_pinter.
Pass 3 of while loop:
3 < 3 falsePass 2 of for loop:
i = 1
left_pointer = 2
Right_pointer = 3
Pass 1 of while loop
2 < 3
sum = -1 + 1 +2 = 2
if (1 < 2)
closest_sum = 2Hence our result is “2”
Solution in C++
#include<iostream>
#include<vector>
using namespace std;
void threeSumClosest (vector<int> &arr, int key)
{
sort(arr.begin(), arr.end());
int closest_sum = arr[0] + arr[1] + arr[2];
int len = arr.size();
for (int i = 0; i <= len - 3; i++)
{
int left_pointer = i + 1;
int right_pointer = len - 1;
while (left_pointer < right_pointer)
{
int sum = arr[i] + arr[left_pointer] + arr[right_pointer];
if (abs(sum - key) < abs(closest_sum - key))
closest_sum = sum;
if (sum < key)
{
left_pointer ++;
} else if (sum > key)
{
right_pointer--;
}
}
}
cout<< "The closest to the key "<< key << " is = "<< closest_sum << endl;
}
int main() {
vector<int> arr;
int key = 1;
arr.push_back(-1);
arr.push_back(2);
arr.push_back(1);
arr.push_back(4);
threeSumClosest(arr, key);
return 0;
}Output:
The closest to the key 1 is = 2