Two Sum 兩數(shù)之和
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].
思路分析
- 參數(shù)：一個數(shù)字?jǐn)?shù)組nums涂召，一個目標(biāo)數(shù)target鲤桥。
- 目標(biāo)：讓找到兩個數(shù)字(同一個數(shù)字不能使用兩次)，使其和為target瘪弓。
- 分析：暴力搜索的話是遍歷所有的兩個數(shù)字的組合計算其和，這樣節(jié)省了空間，但是時間復(fù)雜度高泉坐。為了減少時間的復(fù)雜度，需要用空間來換裳仆。
只遍歷一次數(shù)組腕让，在遍歷的同時將數(shù)據(jù)使用HashMap存儲起來，翻轉(zhuǎn)key和value歧斟，建立數(shù)字和其坐標(biāo)位置之間的映射纯丸。HashMap 是常數(shù)級的查找效率，這樣在遍歷數(shù)組的時候静袖，用 target 減去遍歷到的數(shù)字觉鼻，就是另一個需要的數(shù)字了。直接在 HashMap 中查找其是否存在即可队橙。
由于當(dāng)前數(shù)字在HashMap中還不存在坠陈，所以不會出現(xiàn)同一個數(shù)字使用兩次的情況萨惑。比如 target 是4，遍歷到了一個2仇矾，另外一個2還未進(jìn)入HashMap中庸蔼，肯定就是要找的值。
整個實(shí)現(xiàn)步驟為：遍歷一遍數(shù)組贮匕，查找target 減去當(dāng)前數(shù)字是否存在于HashMap中姐仅；如果不存在，則建立 HashMap 映射粗合。代碼如下：
Go代碼
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for k, v := range nums {
idx, ok := m[target - v]
if ok {
return []int{idx, k}
}
m[v] = k
}
return nil
}
// nums := []int{2, 7, 11, 15}
// target := 9
// result [1 0]
