3Sum Closest

Problem Statement

The task is to identify three integers within a given array, nums, such that their cumulative sum is closest to a provided integer, target. The array nums will have a length n, and you are required to return the sum of these three integers. For every provided input, there exists precisely one optimal solution, thus implying that a unique closest sum can always be determined.

Examples

Example 1

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

Example 2

Input:

nums = [0,0,0], target = 1

Output:

0

Explanation:

The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Approach and Intuition

1. Sorting the Array:

   • Begin by sorting the array nums. Sorting helps in efficiently finding the required numbers as it allows usage of pointer techniques to decide which direction to move within the array.

2. Initialize Tracking Variables:

   • Start with closest_sum variable to store the closest sum found relative to the target during the iteration. It is initially set to the sum of the first three numbers of the sorted array.

3. Using Two Pointers:

   • For each element in nums, treat it as a potential first element of the triplet.
   • Use two additional pointers—start and end—initialized to the next element in the array and the last element, respectively.

4. Evaluate Sums:

   • Calculate the sum of elements at these three pointers. Compare this sum with the target.
   • If the sum is equal to the target, return this sum immediately as this is the closest possible.
   • If the sum is less than the target, move the start pointer one step to the right to increase the sum.
   • If the sum is greater than the target, move the end pointer one step to the left to reduce the sum.

5. Update Closest Sum:

   • Keep a check if the absolute difference between the current sum and target is smaller than any previously found. If so, update closest_sum with this current sum.

6. Iterate and Optimize:

   • Continue the process for each element as the potential first element until the entire array has been considered.
   • The answer after finishing the array traversal will be stored in closest_sum.

Key Considerations:

• Handling of near elements: The method is particularly efficient for non-distinct elements as well, providing the closest possible sum irrespective of duplicates.
• Efficiency: This approach ensures that the problem is tackled in O(n^2) time complexity because of the nested structure of checking combinations through pointers.
• Edge Cases: For arrays where all elements are the same, or when target is minimum or maximum, the same technique applies transparently and efficiently.

Example Walkthroughs:

• For the input nums = [-1,2,1,-4], target = 1, after sorting and evaluating, we find that the closest sum possible is 2 derived from the combination (-1, 2, 1).
• For nums = [0,0,0], target = 1, though the nums contain identical elements, the sum calculation of (0 + 0 + 0) = 0 is straightforward and closest to 1.

This approach leverages the sorted property of the array to effectively narrow down potential sums, ensuring that the closest sum to the target is quickly and accurately found.

Solutions

class Solution {
public:
    int closestThreeSum(vector<int>& numbers, int targetValue) {
        int minDiff = INT_MAX;
        int length = numbers.size();
        sort(numbers.begin(), numbers.end());
        for (int i = 0; i < length && minDiff != 0; ++i) {
            for (int j = i + 1; j < length - 1; ++j) {
                int tgt = targetValue - numbers[i] - numbers[j];
                auto it = lower_bound(numbers.begin() + j + 1, numbers.end(), tgt);
                int higher = it - numbers.begin();
                int lower = higher - 1;
                if (higher < length && abs(tgt - numbers[higher]) < abs(minDiff)) {
                    minDiff = tgt - numbers[higher];
                }
                if (lower > j && abs(tgt - numbers[lower]) < abs(minDiff)) {
                    minDiff = tgt - numbers[lower];
                }
            }
        }
        return targetValue - minDiff;
    }
};