Input: [-1, 2, 1, -4] Key = 1
Output:
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)
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 the 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 the 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 the two sum problem.
Now we take 2 pointers, left_pointer starting from the 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 false
Pass 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 = 2 Hence 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