第 13 天

两数之和

难度：简单

题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

题解

思路一：双循环

第一次接触题目，首先肯定是想到暴力解法，通过双循环遍历数组；

注意用 indexof 也是一种循环方式。

var twoSum = function(nums, target) {
    for(let i = 0, len = nums.length;i < len;i++){
        // 因为同一元素不允许重复出现，所以从i的下一位开始遍历
        for(let j = i + 1;j < len;j++) {
            if(nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    // 所有样例都是有返回结果的，这里无所谓
    return [-1, -1];
};

思路二：用 map

方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

对象写法：

var twoSum = function(nums, target) {
//创建空对象obj
  const obj = {}
  // 拿到nums的长度
  const len = nums.length
  // 遍历数组
  for(let i=0;i<len;i++){
    // 可以把target-数组元素的值作为obj的键，不存在则存储，存在就返回键和i
    if(obj[target - nums[i]] !== undefined){
      return [obj[target - nums[i]],i]
    }
    //不存在则将nums[i]的值作为键，i为值
    obj[nums[i]] = i
  }
};

Map 写法：

var twoSum = function(nums, target) {
  const map = new Map()
  for(let i = 0; i < nums.length; i++){
    if(map.has(target - nums[i])){
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i] , i)
  }
};

总结

很多题用双循环解题都可以转化为 map，减少一层循环的复杂度。