1. 题目

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

2. 解答

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

• 时间复杂度：O(N^2)，最坏的情况是数组中任意两个数都要匹配一次。

• 空间复杂度：O(1)

• 执行用时：72 ms, 在所有 JavaScript 提交中击败了97.20%的用户

  内存消耗：38 MB, 在所有 JavaScript 提交中击败了56.37%的用户

3. 答案 2

由于暴力搜索的方法是遍历所有的两个数字的组合，然后算其和，这样虽然节省了空间，但是时间复杂度高，一般来说，为了减少时间的复杂度，需要使用空间来换，这里我们想要使用线性的时间复杂度来解决问题，也就是说，只能遍历一个数字，而另外一个数字呢，可以事先将其存储起来，使用一个Map数据结构，来建立数字和坐标之间的映射关系，由于Map是常数级查找效率, 这样在遍历数组的时候, 用target减去遍历到的数字，就是另外一个需要的数字了，直接在Map中查找其是否存在即可，需要注意的是，判断查找的数字不是第一个数字，比如target是4，遍历得到了一个2，那么另外一个2不能是之前的那个2，整个实现步骤为: 先遍历一遍数组，建立Map映射，然后再遍历一遍，开始查找，找到则记录index。

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number[]}
 5  */
 6 var twoSum = function (nums, target) {
 7   const map = new Map();
 8   for (let i = 0; i < nums.length; i++) {
 9     // 遍历到当前元素的时候, 判断map中是否存在目标值
10     if (map.has(target - nums[i])) {
11       // 只循环一遍能够保证 索引不重复
12       return [i, map.get(target - nums[i])]
13     }
14     map.set(nums[i], i)
15   }
16   return [];
17 };

• 时间复杂度: O(N), 其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

• 空间复杂度: O(N), 其中 N 是数组中的元素数量。主要为哈希表的开销。

• 执行用时：76 ms, 在所有 JavaScript 提交中击败了91.99%的用户

  内存消耗：38 MB, 在所有 JavaScript 提交中击败了55.75%的用户

LeetCode 热题 HOT 100 之 两数之和

原文：https://www.cnblogs.com/wzezhu/p/14403237.html