Sum Closest Algorithm
The Sum Closest Algorithm is an algorithmic approach to find the pair or set of elements from an array or list whose sum is closest to a given target value. This problem is commonly encountered in various applications, such as financial portfolio management, optimization, and data analysis. The algorithm aims to minimize the absolute difference between the target value and the sum of the chosen elements from the array. The algorithm usually involves sorting the input array, using two pointers (or indices) to traverse the array, and updating the closest sum as the pointers move.
There are several variations of the Sum Closest Algorithm, including the Two Pointers Method and the Modified Binary Search, which cater to different problem constraints, such as the number of elements to be summed or the size of the input array. These algorithms generally have time complexities ranging from O(nlogn) to O(n^2), depending on the implementation. The Two Pointers Method, for instance, sorts the input array first and then uses two indices to traverse the array, updating the closest sum as they move. This method has a time complexity of O(nlogn) due to the sorting step. The Modified Binary Search approach, on the other hand, involves searching for the complement of an element in the array, and its time complexity depends on the search algorithm used. Overall, the Sum Closest Algorithm provides an efficient and effective means of finding the elements in an array with the closest sum to a target value, making it a valuable tool in various applications.
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
sort(num.begin(), num.end());
int delta = INT_MAX;
int closest = 0;
for (int i = 0; i < num.size(); i++) {
int start = i + 1;
int limit = num.size() - 1;
while (start < limit) {
int sum = num[i] + num[start] + num[limit];
if (abs(sum - target) < delta) {
delta = abs(sum - target);
closest = sum;
}
if (sum == target) {
return target;
} else if (sum < target) {
start++;
} else {
limit--;
}
}
}
return closest;
}
};
