3Sum Closest

So I Heard You Like ...Sums? My Take on 3Sum Closes

Alright, it's becoming a habit to share my first reaction to these problems, so here we go. When I saw "3Sum Closest," my brain pretty much went:

I mean, I'd already conquered 2Sum, 3Sum, and even battled through 4Sum. Don't get me wrong, I love a good trilogy (and its questionable fourth installment), but this felt like a sequel I didn't ask for.

But this one is a little different. It’s got a fun twist! We don't need to find a triplet that equals a target. Instead, we need to find the one whose sum is the closest.

There could be many triplets, and we need to figure out which one is the "closest." So, what does "closer" even mean here? Well, think of it like a number line. You just subtract the triplet's sum from the target and take the absolute value. The smaller that result, the cozier you are to the target. That's our mission.

The game plan is actually pretty similar to the original 3Sum. Ohh! and we need to sort our vector/array before we do anything. Now you start with a for loop that runs through each element, let's call its iterator i.

From there, we get to use the classic two-pointer strategy. We'll plant a left pointer at i + 1 and a right pointer at the very end of the array. Now we have our triplet!

With our three numbers, we calculate the sum. Then, as I mentioned, we find the current_difference between this sum and our target. This is where we need to keep score. We'll have a couple of variables, min_difference and closest_sum, to remember the best we've seen so far.

Every time we calculate a new sum, we check: is this new guy even closer than our current champion?

if (abs(target - sum) < min_difference) {
    min_difference = abs(target - sum);
    closest_sum = sum;
}

Simple enough, right? Now we just need to move our pointers in that slick, efficient way we all learned from the 2Sum problem.

if (sum < target) {
    left++;
} else if (sum > target) {
    right--;
} else {
    return sum;
}

Now, you might be looking at that else block and thinking, "Hold on, why are you returning the sum right away?"

Think about it for a second. If our sum actually equals the target, can we possibly get any closer? Nope! That's a bullseye. It's the undisputed, all-time champion of "closest." So, we can just return it and call it a day.

But if we get through the whole loop and never hit that perfect match, no sweat! Our closest_sum variable has been faithfully remembering the next best thing the whole time. We just return that at the very end.

And that's it! That's the 3Sum Closest problem for you.

Happy Coding!