Two_Sum.js

// Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

// You can return the answer in any order.

// Example 1:

// Input: nums = [2,7,11,15], target = 9
// Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

// Example 2:

// Input: nums = [3,2,4], target = 6
// Output: [1,2]

// Example 3:

// Input: nums = [3,3], target = 6
// Output: [0,1]

// Constraints:

//     2 <= nums.length <= 104
//     -109 <= nums[i] <= 109
//     -109 <= target <= 109
//     Only one valid answer exists.

// Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let arrind = {},
    index1,
    index2;
  for (let key in nums)
    if (arrind[nums[key]] === undefined) arrind[nums[key]] = [key];
    else arrind[nums[key]].push(key);
  nums.sort((a, b) => a - b);
  let arr = [],
    i = 0,
    l = nums.length - 1;
  // O(n^2) way below
  // for(let i=0;i<nums.length;i++)
  // for(let j=i+1;j<nums.length;j++)
  // if(nums[i]+nums[j]===target) arr.push(i,j);
  // O(nlogn) way below
  while (i < l) {
    if (nums[i] + nums[l] === target) {
      index1 = arrind[nums[i]].shift();
      index2 = arrind[nums[l]].shift();
      arr.push(index1, index2);
      break;
    } else if (nums[i] + nums[l] > target) l--;
    else if (nums[i] + nums[l] < target) i++;
  }
  return arr;
};