# 1.两数之和

# 题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // do some things...
};

# 错解题意

由于审题不清，我们很容易得到以下思路：

• 题目：两数之和
• 参数：
  • nums: number[]
  • target: number
• 结果：
  • number[]

所以就会沿着自己的思路下来，得到以下错误的题解：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var num1 = nums.shift();
    var expectNum = target - num1;
    return nums.includes(expectNum) ? [num1, expectNum] : twoSum(nums, target);
};

# 错解题意二

由于对于题目了解不透彻，有一部分人就会对题意理解不透彻（比如我）：

• 题目：两数之和
• 参数：
  • nums: number[]
  • target: number
• 结果：
  • number[]
• 假设：
  • 每种输入只会对应一个答案
  • 不能重复利用这个数组中同样的元素（不可以一个索引使用两遍[注：这里的理解是使用过程中，而不是return]）

所以就会沿着这个思路下来，自己内心会否定自己，会认为双层for循环的暴力破解法 “违反了不能重复利用这个数组中同样的元素” 这条规定；会认为下图的思路是错误的：

错误理解题意：认为后三个元素，每个元素使用超过了两遍以上，即违反规定。

# 错解题意三（排序+双指针）

我们可以先对数组进行一次排序， 比如进行一次升序排序， 这样我们就可以使用双指针中的头尾指针法来解决这个问题。

拿题目中的 [2, 7, 11, 15] 为例，由于数组本身就是有序的，因此我们进行一次升序排列之后仍然是 [2, 7, 11,15] 。

之后我们建立头尾指针，分别指向 2 和 15。我们将两者相加即 2 + 15 = 17。

17 大于我们要找的目标值 9,因此我们需要将尾指针前移动，由于我们的数组是升序的，这样我们加起来的值才可能变小。经过次移动之后，头尾指针分别指向 2 和 11，此时 2+11=13。

接下来就一直向前得到对应的值 [2, 7] 也就是返回 [0, 1] 就好了对吧。

你以为结束了，NO！继续看下面

那么，比如我们需要的索引是 [1, 2],顺序就应该是这样的：

• 1、索引0 - 分别与索引 3,2,1 进行匹配
• 2、无果，头指针进一，尾指针复位末位
• 3、索引1 - 分别与索引 3,2进行匹配
• 4、匹配结果是 [1,2]

所以，emm...这是正确的？？？ 不！

我们仔细看一下题意，返回的是 nums: number[] 匹配出来对应的索引值，所以在最开始进行的排序就是错误的。 啊哈哈~

希望大家针对算法的题目，切记要审题清晰，多读几遍没毛病的。一旦题意不明，写再多的代码都的不到正确答案。

# 正确题解方法

• 题目：两数之和
• 参数：
  • nums: number[]
  • target: number
• 结果：
  • number[]
• 假设：
  • 每种输入只会对应一个答案
  • 不能重复利用这个数组中同样的元素（return的时候不可以出现[4, 4]这样索引一致的结果）

下面是我提供的几种解法:

# 解法一：双for暴力破解法

# 思路

我们对数组进行遍历，并从遍历项索引值+1的项开始第二层循环。类似于排列组合C(nums.length, 2)。 在这里是C(4, 2) = (4*3) / (2*1) = 6; 也可以直接看下图：

排列组合-百度百科

# 代码

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

这种方法虽然让我们完成了题解，阅读起来也清晰明了。但是这种方法的时间复杂度为O(n!)，属于效率低下的一种方法，所以我们在开发时间允许的情况下，需要去寻找一种时间复杂度更低的算法。

# 解法二：空间换时间

# 思路

我们对数组进行遍历，遍历每一项的时候都进行期望值判断 target - nums[i] (其中 i 是当前数组的索引)是否在之前遍历过了，如果存在则直接返回即可。如果不存在，我们将其存起来，然后继续遍历下一项。

# 代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var n = nums.length;
    var mapper = {};
    for (var i = 0; i < n; i++) {
        if (target - nums[i] in mapper) {
            return [mapper[target - nums[i]], i];
        } else {
            mapper[nums[i]] = i;
        }
    }
};

// 或

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i ++) {
        const otherIndex = map.get(target - nums[i]);
        if (otherIndex !== undefined) return [otherIndex, i];
        map.set(nums[i], i);
    }
};

这种方法能够在线性的时间内完成，但是相应地我们使用了额外的 O(n) 空间，这在很多情况下是值得的，不但可以使代码实现该算法，而且mapper中的数据天然有序，因为mapper的键值对为value => index(value和index为nums中的每一项的值和索引)。