Refactor Nested For Loop

Question

Instructions

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

How can I refactor this to eliminate the nested for-loop? I'd like to get the time complexity down.

Code

const twoSum = function(nums, target) {
    for(let i in nums){
      for(let j in nums) {
        if(nums[i] + nums[j] === target && nums[i] != nums[j]) {
            return [i, j];
        }
      }
    }
};

console.log(twoSum([2, 7, 11, 15], 9));

Answer 1

You can save the difference of each element with the target inside an object with the result as keys and the index as values. This will make checking for the existence of an element inside an object without looping though the whole content. In a different loop check if the array elements exist in the object, if they do then you have got the pair. The additional condition is to prevent comparing an element with itself.

const twoSum = function(nums, target) {  
  const temp = {};
  for(let i=0; i<nums.length; i++) {
    temp[target - nums[i]] = i;
  }

  for(let i=0; i<nums.length-1; i++) {
    if(temp[nums[i]] && temp[nums[i]] !== i) {
      return [i, temp[nums[i]]]
    }
  }
};

console.log(twoSum([2, 11, 7, 17], 9));
console.log(twoSum([1, 3, 4, 2], 6));