給定一個整數數組，如果兩個元素值之和等於給定的值，則返回它們的索引。
你可以假定只有一個明確的答案，而且不能使用同一元素兩次。
原題
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}