题解 | #两数之和#

最开始我想的比较简单，采用了一个嵌套循环的解法：

package main

/**
 *
 * @param numbers int整型一维数组
 * @param target int整型
 * @return int整型一维数组
 */
func twoSum(numbers []int, target int) []int {
	// write code here
	for i := 0; i < len(numbers)-1; i++ {
		for j := i + 1; j < len(numbers); j++ {
			if numbers[i]+numbers[j] == target {
				return []int{i + 1, j + 1}
			}
		}
	}
	return []int{}
}

但是这道题超时了，题目要求的时间复杂度是O(nlogn），这个解法明显不行。

尝试另外一种解法，最坏的情况只用遍历一次数组就能得到答案：

package main

/**
 *
 * @param numbers int整型一维数组
 * @param target int整型
 * @return int整型一维数组
 */
func twoSum(numbers []int, target int) []int {
	// write code here
	var m = make(map[int]int)

	for i := 0; i < len(numbers); i++ {
		v, ok := m[target-numbers[i]]
		if ok {
			return []int{v + 1, i + 1}
		} else {
			m[numbers[i]] = i
		}
	}
	return []int{}
}

实际的求解时间只有62ms。