LeetCode Problem 1 - Two Sum

最近开始在 LeetCode 网站上刷题，准备练练脑子。因为经常不动脑，感觉快生锈了。这个是第一题，比较简单。所有的解题代码都放在 Github 上。

问题描述：

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].

题目描述的很清楚了，就是要从整数列表里面找出符合需求的两个数字，他们之和等于给定的目标值。输入是整数列表，输出是两个数字下标的列表。从给的例子上看，我们可以假设返回的列表，下标小的放在前面，比如是 [0, 1] 而不是 [1, 0]。那假如没有找到符合要求的数字呢，应该返回什么呢？题目里面没有明确说明，我自己觉得这里应该返回一个空值。

思路一

首先，我们可以想到一种最简单的方法，就是遍历所有组合，这种方法比较暴力也很有效。下面的代码用 go 语言编写：

func twoSum(nums []int, target int) []int {
	n := len(nums)

	if n < 2 {
		return nil
	}

	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

这个方法没什么好解释的，它的时间复杂度是O(n^2)。

思路二

如果我们要降低时间复杂度，就必须减少迭代的次数。可以想到的一个优化思路是，针对数组进行排序，然后定义两个指针，分别从头和尾两个方向逼近，看起来有点像快速排序。如果指针指向的两个数之和大于目标值，则右边的指针左移。反之，左边的指针右移。直到找到符合需求的两个数。因为排序的最佳时间复杂度可以达到O(nlogn)，接下来只遍历一次，时间复杂度是O(n)，所以总的时间复杂度为 O(nlogn)。

这是一个不错的思路，但是这道题目要返回数字的下标，但是如果我们先排序会导致顺序就和初始状态不一样，所以还得想办法记录，所以这个思路最终实现也挺别扭的，就放弃了。

思路三

回到题目，我们要求出 a+b=target，反过来看，如果我们当前遍历的数字是 a，也就是我们要看 target - a 这个结果在数组里面是否存在。为了加快查找的效率，我们可以用额外的空间换时间效率，哈希表是一个很好的策略。在遍历的时候我们把每个数字和它对应的坐标保存到一个哈希表中。相应的代码如下：

func twoSum(nums []int, target int) []int {
	tbl := make(map[int]int, len(nums))

	for i, v := range nums {
		if j, ok := tbl[target-v]; ok {
			return []int{j, i}
		}

		tbl[v] = i
	}

	return nil
}

完整代码

完整的代码参见这里，以及测试代码。