Solving Three Number Sum

Today, we will be solving the three number sum problem together. In a previous article we went over the two number sum problem and discovered a brute force solution for that. Today we are going to again take the brute force approach to figure out the solution to the Three Number Sum Problem.

For this problem we receive two inputs, an array and a target sum that three individual numbers in the array need to add up to and if no three add up to the target sum, we return an empty array. So we have to write a function that finds all triplets that add up to the target sum in our input. Lets get started..

Here is our starter code, for this exercise we are going to continue with the knowledge that our input array is already sorted. If we think back to our two number sum problem, the next step should be obvious. We need to loop through our input array and do something. When we loop through we need to check a condition and see if three numbers add up to our target sum but we can’t just achieve this with one loop unfortunately, our time complexity will suffer in this problem as we start another loop through our input array but this time instead of using a for loop, we will use a while loop that will compare 3 numbers, the first number being array[i], the second being array[i + 1] and third being array[array.length — 1]. Now these need to change as we get an answer or if the sum of the numbers is too large or too small so we need to store these values in variables and change them as needed depending on the output of our three values. Here is what some of that will look like in code..

Now that we have our variables declared, we need to check our conditionals. The first conditional being if the currentSum variable is equal to the targetSum input and if it is we need to push those three numbers from currentSum into our resultsArray and increment our left variable and decrement our right variable so we can check the next numbers in our array. Our next conditional is going to check if the currentSum is less than the targetSum and if it is, all we do is increment our left variable. On the opposite end of that if our currentSum is greater than our targetSum, we only decrement the right variable. Notice that the only conditional that affects our result is the first one where currentSum === targetSum.

And there it is. Our solution to our three number sum problem. Going over our issue again, we instantiate a result array, loop through our input array twice keeping track of the first number, the second number and the last number in the input array and incrementing their values once we reach a certain condition and then at the end of that we return a result array. Thats all folks, see ya next time!