装逼了 用的二叉搜索树 效率低到爆
package main
import "fmt"
func main() {
var nums = []int{217,231,523,52,547,243,648,509,415,149,689,710,265,187,370,56,977,182,400,329,471,805,955,989,255,766,38,566,79,843,295,229,988,108,781,619,704,542,335,307,359,907,727,959,161,699,123,650,147,459,657,188,304,268,405,685,620,721,351,570,899,60,388,771,24,659,425,440,508,373,32,645,409,272,356,175,533,740,370,152,34,510,745,251,227,494,258,527,817,773,178,194,860,387,627,851,449,736,15,212,529,950,316,28,65,484,968,63,4,643,795,669,203,677,139,636,289,555,430,849,150,493,301,377,240,873,965,441,230,349,447,470}
res := twoSum(nums,718)
fmt.Println(res)
}
type Node struct {
Key []int
Value int
Left *Node
Right *Node
}
var Head1 *Node = nil
func twoSum(nums []int, target int) []int {
var res []int
lens := len(nums)
for i:=0;i<lens;i++ {
put(Head1,i,nums[i])
}
for i:=0;i<lens;i++ {
resNode,errCode := get(Head1,target-nums[i])
if errCode == 0 {
for _,v := range resNode.Key{
if v != i{
res = append(res,i,v)
Head1 = nil
return res
}
}
}
}
Head1 = nil
return res
}
func get(head *Node,value int) (*Node,int){
var defRes *Node
if head == nil{
return defRes,1
}
if value > head.Value{
return get(head.Right,value)
}else if value < head.Value{
return get(head.Left,value)
}else{
return head,0
}
}
func put(head *Node,key int,value int) *Node{
if head == nil{
var node = new(Node)
node.Key = append(node.Key,key)
node.Value = value
if key == 0{
Head1 = node
}
return node
}
if value < head.Value{
head.Left = put(head.Left,key,value)
return head
}else if value > head.Value{
head.Right = put(head.Right,key,value)
return head
}else{
head.Key = append(head.Key,key)
return head
}
}
下面是golang自带map实现（大部分golang方法）
func twoSum(nums []int, target int) []int {
var res []int
var mp = make(map[int]int)
for k,v := range nums{
mp[v] = k
}
for k,v := range nums{
if kk,ok := mp[target-v];ok && k != kk{
res = append(res,k,kk)
return res
}
}
return res
}
