# 题目描述

给定一个整数数组 nums 和一个整数目标值 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]

题目链接:两数之和 (opens new window)

# 解法

# 双 for

第一个想到的就是 for 两次,然后做判断。 这个没啥可说的,暴力解法,穷举+判断即可。

let twoSum = function(nums, target) {
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (target == nums[i] + nums[j] && i !== j) {
        return [i, j];
      }
    }
  }
};

**思路:**循环+判断

复杂度

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

# 静态 Map

因为描述有说,他的值不可用两次,就想到了可以用 ES6 的 Set 数据结构,先把所有的值转为 Set,相当于做了一个去重,然后在求和。

后来发现 Set 存上了,索引怎么取?不如直接用对象,但是对象的键只能为字符串,后面还得做一次数值转换。

看了评论去大神的写法,换用了 Map,新知识 Get!

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

思路:

  1. 先将 nums 转为 Map 类型的,值为健,健为值。
  2. 然后 for nums 时判断 map 中是否存在 diff
  3. 有 diff 在判断是否索引一样,如果不一样,直接 return,否则继续

复杂度

  • 时间复杂度:O(m+n)
  • 空间复杂度:O(1)

# 动态 Map

其实把上面的改一改,在每次 for 的时候,判断是否有差值,如果就去判断,有没就去添加。

这样 for 一次就可以了。

let twoSum = function(nums, target) {
  let len = nums.length;
  let map = new Map();
  for (let i = 0; i < len; i++) {
    console.log(i, nums[i]);
    let diff = target - nums[i];
    if (map.has(diff) && map.get(diff) !== i) {
      return [map.get(diff), i];
    } else {
      map.set(nums[i], i);
    }
  }
};

思路:

  1. 和上面的差不多,不过是一边 for 的时候做 diff 判断
  2. 无 diff 去 set
  3. 有 diff 判断即可

复杂度

  1. 时间复杂度:O(n)
  2. 空间复杂度:O(1)

# 总结

Map:以前只是文档看过,对于它的应用场景一直很模糊,实际工作中基本没有用到,这次也算是熟悉一些。

这次也算是加深了印象,对于应用场景也有了一些了解。

上次更新: 4/23/2021, 2:14:10 PM