LeetCode problem #16–3Sum Closest (JavaScript)

In this LeetCode challenge, we’re given an array of numbers, and asked to find the total of the 3 closest numbers to a given a target. In other words, given the array [1, 2, 3, 4] and a target of 7, we would return 7, as 1 + 2 + 4 = 7. If however the target was 11, then the closest we can get is 2 + 3 + 4 = 9, so we’d return 9.

This challenge is very similar to the 3-sum challenge. The main difference however is that instead of returning all possible combinations, we’re returning the closest combination (we’re actually returning the sum of the closest combination, but that’s not really important for this comparison).

Solution: Contracting Window

Just like with the 3-sum problem, this answer involves first looping through the (ordered) array of numbers. With each number, we then establish a “window”, with its left-hand side on the next number in the array, and the right-hand side on the last number.

We then check if we’ve found the solution, at which point we break out with its sum. If however the total of the 3 numbers is too low, we move the left-hand side of the window in by 1. Likewise, if the total is too high, we move the right-hand side in by 1.

In either of the above cases, we also record the total, if it is closer to the target than any previous record (as we are of course looking for the closest 3-sum here).

Here’s the code: