2019-05-14-TwoSum

• two sum
  From 21:10 - 21:30

• array

• map

My solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var res = [];
    
    // value : index
    var map = {};
    
    // tranfer arr to map
    // attrieve complexity n -> 1
    for(var i=0; i<nums.length; i++){
        map[nums[i]] = i;
    }
    
    // assume: must have and only one solution 
    // looping through the arr, search the rest of value in the map
    for(var j=0; j<nums.length; j++){
        var rest = target - nums[j];
        var index = map[rest];
        
        if(index){
            if(index!==j){
                res.push(j, index);
                return res;
            }
        }
    }
    
};

// Time complexity: O(n)
// Runtime: 48 ms, faster than 99.85% of JavaScript online submissions for Two Sum.
// Memory Usage: 36 MB, less than 16.79% of JavaScript online submissions for Two Sum.

• Other submittion

var twoSum = function(nums, target) {
    for(let i=0;i<nums.length;i++){
        for(let j=0;j<nums.length;j++){
            if(i!==j&&(nums[i]+nums[j]===target)){
                return [i,j];
            }
        }
    }
};

var twoSum = function(nums, target) {
  const map = {};
  
  for(let i = 0; i < nums.length; i++) {
    const currentValue = nums[i];
    const wantedValue = target - currentValue;
    if(map[wantedValue] !== undefined) {
      return [map[wantedValue], i];
    }
    map[currentValue] = i;
  }
};