how to improve performance of nested for loops when comparing values in an array

Question

var twoSum = function(nums, target) {
  for(let i = 0; i < nums.length; i++){
    for(let j = i + 1; j < nums.length; j++){
      if(nums[i] + nums[j] === target){
        return [nums.indexOf(nums[i]), nums.lastIndexOf(nums[j])]
      }
    }
  }
}
function([3,5,3,7,2], 9) //It should return [3, 4] since 7 + 2 = 9

This is a Javascript function and it's iterating over the array of numbers with nested for loops and find a pair that when summed, it equals the target and return their indexes. Since it has a nested for loop it I believe it has O(n^2) or quadratic time complexity, and I was wondering if there is a faster way to do this. I'm just trying to get the first pass solution and after improve upon it. 😁 Thanks in advance!

Answer 1

Create an object that maps each element to its last index. Then loop over each element, and see if target - element is in the object with a different index.

function twoSums(nums, target) {
  const last_index = {};
  nums.forEach((num, i) => last_index[num] = i);
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (diff in last_index && last_index[diff] != i) {
      return [i, last_index[diff]];
    }
  }
}

const list = [3,5,3,7,2];
console.log(twoSums(list, 9));
console.log(twoSums(list, 6));
console.log(twoSums(list, 15));

Looking up an object property is O(1), so this algorithm is O(n).