两数之和

简单

给定一个整数数组 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]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解

暴力枚举

用两个for循环来做，外层for循环每次按顺序取出一个数组元素，并在内层循环中与在它之后的所有元素进行相加。
例如 [0, 1, 2, 3] 第一轮循环取出0，分别跟后面的元素 1, 2, 3 相加，第二轮取出1，分别跟后面的元素 2,3 相加...
因为前面外层循环中取出的元素跟后面的元素都相加过了，所以轮到后面时就不用再跟前面的元素进行相加了
比如外层第一轮循环完，0已经跟 1, 2, 3 都相加过了，所以轮到后面的 1, 2, 3 都不用跟 0 进行相加了
如果某次相加时的和等于目标值，则返回两个元素的下标的数组，return能直接终止循环，结束函数，如果循环完没有符合的，就返回一个空数组

javascript

const nums = [2, 7, 11, 15];
const target = 9;

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

twoSum(nums, target);

哈希表

创建一个map，用来存储元素，key存储元素值，value存储元素的下标
只需要一层循环，每次循环时用 target - 当前循环取到的元素，相差的结果对map进行查找
如果有则说明查找到了，返回该元素的下标和查找到的元素的下标
接着把当前循环到的元素添加到map中，key:元素值，value:元素下标
整个循环结束都没有查找到元素，则返回空数组

例如：
nums:[2, 7, 11, 15]
target:9
map:{}

第一次循环，i=0，取到元素2
用target减去当前循环到的元素：9-2=7, 判断map中是否存在key为7的元素
第一次循环时map中没有任何元素，所以不存在key为7的元素
接着就把元素2和它在数组中的下标0放到map中
map:{2:0}

第二次循环，i=1，取到元素7
用target减去当前循环到的元素：9-7=2, 判断map中是否存在key为2的元素
map为{2:0}，存在key为2元素，它的value为0（也就是下标），所以最终返回[0,1]

javascript

const nums = [2, 7, 11, 15];
const target = 9;

var twoSum = function (nums, target) {
  let len = nums.length
  const map = new Map();

  for (let i = 0; i < len; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]),i];
    }
    map.set(nums[i], i);
  }
  return [];
};

twoSum(nums, target);

两数之和 ​

题解 ​

暴力枚举 ​

哈希表 ​

两数之和

题解

暴力枚举

哈希表