twoSum

问题

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].

解释

输入 [2,7,11,15], 9
输出[0, 1]
因为arr[0] + arr[1] = targert

解法

1. 双遍历，两个for循环。
   时间复杂度有些高，但是可以被accept
2. 用hash表，空间换时间。
   用数组的元素做 key，索引做 value 存入数组。遍历时寻找数组里有没有以 target - key 的元素，如果有的话取出下标返回即可。

var twoSum3 = function(nums, target){
  if ( !Array.isArray(nums) || Object.prototype.toString.call(target) !== "[object Number]" ) return;

  var arr = [],
      i,
      j,
      len = nums.length;

  for ( i = 0; i < len; i ++ ){
    j = arr[ target - nums[i] ];
    if ( j !== undefined  ) return [ j, i ];
    arr[nums[i]] = i;
  }
}