两数之和

发表于 更新于 分类于 阅读次数： 本文字数： 443 阅读时长 ≈ 2 分钟

leetcode 题库里面的一道题，官方讲解得很清楚，记录一下。

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

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

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

解法一，比较容易想到的解法就是暴力求解，嵌套 for 循环，时间复杂度 O（n²），空间复杂度 O(1)。
题目要求，数组中同一个元素在答案里不能重复出现，所以，第二层 for 循环只需要在 i 之后的元素中寻找。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
};

解法二，使用 HASH 表取代内层循环，以空间换时间。
哈希表中储存的是数组中的数字和数字对应的索引，其中：key 为数组中的数字，value 为数字对应的索引，每次循环判断 target 值减去数字值在不在 key 中，在的话就返回数组下标，不在的话就将数字和下标保存在哈希表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 存储出现过的数字和索引，其中 key 为 数字，value 为索引
  const hashTable = {};
  for (let i = 0; i < nums.length; i++) {
    // 当前元素
    const curNum = nums[i];
    // 目标元素
    const anotherNum = target - curNum;
    // 获取目标元素的索引
    const anotherNumIndex = hashTable[anotherNum];
    // 如果哈希表中存在
    if (anotherNumIndex !== undefined) {
      return [i, anotherNumIndex];
    } else {
      hashTable[curNum] = i;
    }
  }
};