题目

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:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

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

解法

解法1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func twoSum(nums []int, target int) []int {
	as := make([]int, 2)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				as[0] = i
				as[1] = j
			}
		}
	}

	return as
}

解法2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func twoSum2(nums []int, target int) []int {
	r := make([]int, 2)
	result := make(map[int]int) //key是nums的值,value是值对应的下标
	for n, v := range nums {
		if value, ok := result[target-v]; ok {
			r[0] = value
			r[1] = n
			break
		}
		result[v] = n
	}

	return r
}

总结

解法1就是最简单的循环相加，时间复杂度是O(n^2)。解法2的话因为题目里面是假设了肯定是有解的，那么就直接用一个循环来完成，时间复杂度使用O(n)

源代码

https://github.com/liguoqinjim/leetcodeGo/tree/master/problems/lab0001