LeetCode 1 Two Sum 两数相加-白红宇

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

思考

最直观的数学解题思路是找到全部含有两个元素的子集，然后检测这两个元素之和是否等于 target 。但求子集本来就是代价较高的操作。

考虑到只取两个整数这一特定条件，不难看出，对数组中的每个整数，依次检查它之后的每一个整数，这样也完全遍历了所有的两个整数的子集。对于例子，遍历顺序为：

(2, 7) (2, 11) (2, 15)

(7, 11) (7, 15)

(11, 15)

因此可以写出如下代码：

func twoSum(nums []int, target int) []int {    for i := 0; i < len(nums); i++ {        for j := i + 1; j < len(nums); j++ {            if nums[i]+nums[j] == target {                return []int{i, j}            }        }    }    return []int{}}复制代码

当我们把第4行代码写成 if nums[j] == target - nums[i],换一个角度思考，可以解读为：对每个数nums[i]，检查它后面的是否存在满足 nums[j] == target-a 的nums[j]。

上述代码使用了线性查找，假设 nums 有序，则使用二分查找会更加高效。但由于题目要求返回下标，如果将 nums 排序反倒让事情变得复杂。

另外一种高效的查找是使用 hash table，由于要求返回下标，因此我们可以使用 nums 的值作为 key，而下标作为 valua。

首先将 nums 的元素存入一个名为 m 的 hash table，然后再遍历 nums 。代码如下：

func twoSum(nums []int, target int) []int {    m := make(map[int]int)    for i, e := range nums {        m[e] = i    }    for i, e := range nums {        c := target - e        if _, ok := m[c]; ok && m[c] != i {            return []int{i, m[c]}        }    }    return []int{}}复制代码

可以思考一下如果 nums 中存在重复的数字，代码运行时的情形是怎样的。。

观察这段代码可以发现，相同的循环出现了两次，可以考虑是否在能一次循环中完成。代码如下：

func twoSum(nums []int, target int) []int {    m := make(map[int]int)    for i, e := range nums {        c := target - e        if _, ok := m[c]; ok {            return []int{m[c], i}        }        m[e] = i    }    return []int{}}复制代码

注意 return 语句两个下标的顺序。之前的两段代码都是在当前正在检测的 nums[i] 之后的所有元素中进行查找，而在第三段代码，因为 num[i] 在检测完之后才会被放入 hash table 中，之后再查找，因此为了按原始 nums 的顺序输出下标，此处的顺序有所不同。