给定一个整数数组，如果两个元素值之和等于给定的值，则返回它们的索引。
你可以假定只有一个明确的答案，而且不能使用同一元素两次。
原题
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].
分析
- 目标：两元素的索引
- 依据：两元素的值之和与给定的值是否相等
实现
双重循环
按照题意，脑海最开始浮现的解法是用双重循环，将每个元素和其他元素相加，判断是否和给定值相等即可，相等则返回结束，否则继续。
1func twoSum(nums []int, target int) []int {
2 for i := 0; i < len(nums); i++ {
3 for j := i + 1; j < len(nums); j++ {
4 if nums[i]+nums[j] == target {
5 return []int{i, j}
6 }
7 }
8 }
9
10 return []int{}
11}
Map
但是双重循环的时间复杂度是 O(n^2)，是否有更好的解法呢？ 是否可以使用 Map 呢？如何使用呢？
根据之前的分析，换个角度看，依据可以理解为：给定值和元素之间的差值，那么用 Map 来存储 ‘数值’ => ‘索引’ 的映射的话，则问题迎刃而解。
1func twoSum(nums []int, target int) []int {
2 m := map[int]int{}
3 for i := 0; i < len(nums); i++ {
4 m[nums[i]] = i
5 }
6
7 for i := 0; i < len(nums); i++ {
8 minus := target - nums[i]
9 if j, ok := m[minus]; ok && i != j {
10 return []int{i, j}
11 }
12 }
13
14 return []int{}
15}
Map 改良版
上面的 Map 解法的使得时间复杂度从 O(n^2) 将为 O(n)，确切来说是2*O(n)，因为额外用了一个循环，将整数和其索引的映射存储到 Map 中，如果将两个循环合并在一起呢？
仔细思考了下，于是得出以下优化后的代码，其中 m[nums[i]] = i 放在判断后面，可以避免多次使用同一元素。
1func twoSum(nums []int, target int) []int {
2 m := map[int]int{}
3
4 for i := 0; i < len(nums); i++ {
5 minus := target - nums[i]
6 if j, ok := m[minus]; ok {
7 return []int{i, j}
8 }
9
10 // the code placed here can avoid using the same element twice.
11 m[nums[i]] = i
12 }
13
14 return []int{}
15}
