three Sum Closest Algorithm
The Three Sum Closest Algorithm is a popular problem-solving approach used in computer programming and data processing. It is designed to find three elements in an array, such that the sum of these elements is closest to a given target value. This algorithm is often used to solve problems in coding interviews and competitive programming, as it showcases the candidate's ability to work with arrays and implement efficient algorithms.
The algorithm works by first sorting the input array in ascending order. Then, it initializes variables to keep track of the current minimum difference and the current closest sum. The algorithm iterates through the sorted array, using a fixed pointer and two other pointers, one starting from the beginning of the array and the other starting from the end. The sum of the elements at these pointers is calculated, and the difference between this sum and the target value is compared to the current minimum difference. If the calculated difference is smaller than the current minimum difference, the closest sum is updated. The inner pointers are then adjusted depending on whether the calculated sum is greater or smaller than the target value. This process is repeated until the inner pointers meet or the entire array has been traversed. At the end, the algorithm returns the closest sum that it has found.
/**
* Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
* Return the sum of the three integers. You may assume that each input would have exactly one solution.
* For example, given array S = {-1 2 1 -4}, and target = 1.
* The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
*/
#include <iostream>
#include <vector>
#include <algorithm>
int threeSumClosest(std::vector<int>& nums, int target) {
int closestSum = (nums[0] + nums[1] + nums[2]);
std::sort(nums.begin(), nums.end());
for ( size_t i = 0 ;i < nums.size() - 2; ++i ) {
size_t k = nums.size() - 1;
size_t j = i + 1;
while( j < k ) {
int currSum = (nums[i] + nums[j] + nums[k]);
if ( currSum == target ) {
return currSum;
}
if ( abs(target - closestSum) > abs(target - currSum)) {
closestSum = currSum;
}
if ( currSum > target ) {
--k;
} else {
++j;
}
}
}
return closestSum;
}
int main() {
std::vector<int> vec{ -1,2,1,-4 };
std::cout << "Vec:";
for ( auto c : vec ) {
std::cout << c << " ";
}
std::cout << std::endl;
std::cout << "Three sum closest to 1 in above vector is :" << threeSumClosest(vec, 1) << std::endl;
return 0;
}
