LeetCode problem #15–3Sum (JavaScript)

In this LeetCode challenge, we’re given an array of numbers, and asked to find all 3-number combinations that add to equal 0.

This is a similar question to the two-sum question, however my approach here will be very different.

Solution: Contracting window

In this solution, we start by sorting the array, and then looping through all of the numbers (excluding the last 2, as we need 3 numbers to be able to make a 3-number sum). For each number, we then establish a window, with its left-hand side immediately after the initial number, and its right-hand side at the end of the array. We then sum together the 3 chosen numbers.

If the sum of the 3 numbers is 0 (our target), we add this solution to the pile of solutions, and then move our window in on both the left and right sides (because if we only moved it in on one side, it would be impossible for it to be a solution).

If however the sum of all 3 numbers is not 0, then we only need to move one side in. If the sum is more than 0, then our right-hand side of the window is brought to the left. If the sum is less than 0, our left-hand side of the window is pushed to the right.

One key part to these 3 stages is the fact that we always move until the numbers change. In other words, when we find a solution, we don’t just move the left and right hand sides 1 place in because he numbers may remain the same, so we move them until the numbers change. The reason for this is that we’re asked to find unique solutions, so we cannot simply return the same 3 numbers just because they are in different places.