1.两数之和

题目类别
哈希表

题目

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

自己思路

本人的思路是根据目标值和数组各项的差值，然后循环判断数组哪项和差值相等，再返回数组下标，这样就导致了可能目标值和数组某项差值等于该项自身值等问题。

大神思路

• 初始化一个 map = new Map()
• 从第一个元素开始遍历 nums
• 获取目标值与 nums[i] 的差值，即 k = target - nums[i] ，判断差值在 map 中是否存在

1. 不存在（ map.has(k) 为 false ） ，则将 nums[i] 加入到 map 中（key为nums[i], value为 i ，方便查找map中是否存在某值，并可以通过 get 方法直接拿到下标）
2. 存在（ map.has(k) ），返回 [map.get(k), i] ，求解结束

• 遍历结束，则 nums 中没有符合条件的两个数，返回 []

var twoSum = function(nums, target) {    
  let map = new Map()    
  for(let i = 0; i< nums.length; i++) {        
    let k = target-nums[i]        
    if(map.has(k)) {            
      return [map.get(k), i]        
    }        
    map.set(nums[i], i)    
  }    
  return [];
};  // 时间复杂度O(n)

其他解法

1. 暴力法

• 使用两层循环，外层循环计算 当前元素与target之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标。
• 时间复杂度： O(n^2)

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
  for(var i = 0; i<nums.length; i++) {
    var dif = target - nums[i];
    // j = i+1 的目的是减少重复计算和避免两个元素下标相同
    for(var j = i+1;j<nums.length;j++) {
      if(nums[j] == dif)
        return [i,j]
    }
  }
}

2. 利用数组减少查询时间

• 使用一层循环，每遍历到一个元素就计算该元素与 target 之间的差值 dif，然后以 dif为下标到数组temp中寻找，如果 temp[dif] 有值(即不是 undefined)，则返回两个元素在数组 nums 的下标，如果没有找到，则将当前元素存入数组 temp 中。
• 时间复杂度：O(n)

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
  var temp = []
  for(var i = 0;i<nums.length;i++) {
    var dir = target - nums[i];
    if(temp[dif] != undefined){
      return [temp[dir], i];
    }
    temp[nums[i]] = i;
  }
}