LeetCode–两数之和

题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题：

1.枚举

var twoSum = function(nums, target) {
  let arr = [],
    len = nums.length

  for(let i = 0; i < len - 1; i++){
    for(let j = i+1; j< len; j++){
      if((nums[i] + nums[j]) == target){
        arr.push(i,j)
      }
    }
  }
  return arr
};

缺点：1.双重循环则时间复杂度 为O(N²)

2. Map 或者 对象（{}）

减少查询时间，通过key,val模式快速定位将时间复杂度降到 O(1)，但是这题时间复杂度可以为O(N)

let twoSum = function(nums, target){
  let len = nums.length,
    numMap = new Map()

  for(let i = 0; i < len;i++){
    if(numMap.has(target - nums[i])){
      return [numMap.get(target - nums[i]),i]
    }
    numMap.set(nums[i],i)
  }
}

同样空间复杂度提高到了O(N)，通过空间换时间。