題目
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].
解題思路
方案一
兩層循環(huán)堡掏，遍歷所有可能性祭饭，找到目標(biāo)解
func twoSum(nums []int, target int) (ret []int) {
numLen := len(nums)
for i := 0; i < numLen-1; i++ {
// fmt.Printf("%d: %d\n", i, nums[i])
for j := i + 1; j < numLen; j++ {
sum := nums[i] + nums[j]
// fmt.Printf("sum:%d = %d + %d\n", sum, nums[i], nums[j])
if target == sum {
ret = []int{i, j}
}
}
}
return ret
}
方案二
將數(shù)組中的值val和位置pos對(duì)應(yīng)的鍵值對(duì)放入map中，通過hash表查找使val2 = target - val 的值鹤耍，如果找到則返回結(jié)果城豁，找不到苟穆，則將當(dāng)前值插入map
注意
如果先把所有值都放入map中，如果目標(biāo)結(jié)果是兩個(gè)相同值相加得到的唱星，則不能找到目標(biāo)結(jié)果,比如
nums = []int{3,3}, target = 6
func twoSum(nums []int, target int) []int {
var numMap map[int]int
numMap = make(map[int]int)
var ret []int
for index, val := range nums {
val2 := target - val
fmt.Printf("val:%+v, index:%+v, val2:%+v\n", val, index, val2)
index2, ok := numMap[val2]
if ok && index != index2 {
ret = []int{index, index2}
break
}
numMap[val] = index
}
fmt.Printf("numMap:%+v\n", numMap)
return ret
}
測(cè)試
twoSum_test.go
package _1_Two_Sum
import "testing"
func TestTwoSum(t *testing.T) {
var tests = []struct{
input []int
target int
output []int
}{
{[]int{3, 2, 4}, 6, []int{1, 2}},
{[]int{3, 3}, 6, []int{0, 1}},
}
for _, v := range tests {
ret := TwoSum(v.input, v.target)
if ret[0] == v.output[0] && ret[1] == v.output[1] {
t.Logf("pass")
} else if ret[0] == v.output[1] && ret[1] == v.output[0] {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", v.output, ret)
}
}
}
