两数之和

两数之和

难度：简单

题目

给定一个整数数组 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，减少一层循环的复杂度。

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源