經(jīng)典算法 — 兩數(shù)之和

題目描述

• 給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)，并返回他們的數(shù)組下標(biāo)。

/**
 * @param {number []} nums
 * @param {number} target
 * @return {number []}
 */
var twoSum = function(nums, traget) {
  var map = new Map()
  for(let i in nums) {
    if(map.get(traget - nums[i])) {
      return [map.get(traget - nums[i]), i]
    } else {
      map.set(nums[i], i)
    }
  }
  return []
}

• 結(jié)論
  兩數(shù)之和首先是雙遍歷（O(n * n)）。
  也可以遍歷兩次，第一次是把數(shù)組變成一個對象（key是數(shù)值，value是下標(biāo)）。然后在遍歷一次（O(2 * n)）
  本次結(jié)果是用一次遍歷，滿足則返回，不滿足責(zé)放入map集合中