Objective

Given an array of numbers and a target number, find the sum of two numbers from the array that is equal to the target number. May not sum the same index twice.

Brutal Force Solution

Use a nested for loops to check all possible sums in the array and match the target number as it literates. Time Complexity for this solution is O(n^2).

function twoSum(numArray, numTarget)
{
 const arraySize = numArray.length;

 for(let i = 0; i < arraySize; i++){

     for(let j= i + 1; j < arraySize; j++){

       if(numTarget - numArray[i] === numArray[j]){

          return `The sum of indices ${i} and ${j} equals ${numTarget}` 
        }
     }
  }
 return "target not found."
}

//calling 

twoSum([1,2,3], 5)

//returns 'The sum of indices 1 and 2 equals 5'

twoSum([1,2,3], 6) //returns "target not found"

Use key/value Pairs Solution

Instead of thinking the sum of index1 + index2 = target, we can think of index2 = target - index1, then look for index2 in the key/value object which we will store the array values as keys, and array index as value.

The lookup time in objects or hash tables is O(1) constant time, therefore, this implementation improves the time complexity to O(N).

Pseudo code:

1. create an empty object
2. iterate the array with a for loop
3. let num2 = target - num1 (the num2 is the number we want to lookup for in the object)
4. on each iteration add the value/pair to the object
5. if the num2 is in the object, we have found it, return the indexes and the sum

function twoSum(numArray, target){

  const numObject = {} //create an empty object

  for(let eachNum in numArray){

    const otherNum = target - numArray[eachNum]

    if(otherNum in numObject){

      return `${otherNum} + ${numArray[eachNum]} = ${target}`
    }

    numObject[numArray[eachNum]] = eachNum

//adding key/value has to go after the if statement to avoid adding the same index twice.
  }

  return "target not found"
}

twoSum([1,2,3,4,5], 8) //output: '3 + 5 = 8'
twoSum([1,2,3,4,5], 10) //"target not found"