力扣1.两数之和（JavaScript版本）

题目详情

给定一个整数数组 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 <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

进阶:

你可以想出一个时间复杂度小于O(n²) 的算法吗？

题解

方法一：暴力解法

思路

枚举数组中的每一个数x，寻找数组中是否存在target - x。

因为每个x之前的数都匹配过了，不需要再重复匹配，我们只需要查找x之后是否存在target - x即可。

实现

/**
 * @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];
      }
    }
  }
  return [];

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

• 时间复杂度：O(N²)，其中N是数组中的元素量。最坏的情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：O(1)。

方法二：哈希表

思路

要想降低时间复杂度，哈希表可以有效地将时间复杂度从O(N)降到O(1)。

我们先创建一个哈希表，对于每个x，我们先查询哈希表中是否存在target - x，如果不存在，则将x插入到哈希表中，如果存在则返回下标。

实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const index = map.get(target - nums[i]);
    if (typeof index !== "undefined") {
      return [index, i];
    }
    map.set(nums[i], i);
  }
  return [];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

• 时间复杂度：O(N)，其中N是数组中的元素量。对于每一个元素x，我们可以O(1)地寻找target - x。
• 空间复杂度：O(N)，其中N是数组中的元素量。主要为哈希表的开销。

提交结果对比