Leetcode上的two sum算法用golang实现
two sum问题 :
Given nums = [2,7,11,15],target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
解题一
一般思路:
package main import ( "fmt" ) func twoSum(nums []int,target int) []int { for i,v1 := range nums { if i+1 != len(nums) { for j,v2 := range nums[i+1:] { if target == (v1 + v2) { return []int{i,i + j + 1} } } } } return []int{} } func main() { nums := []int{2,15} fmt.Println(nums[0:]) target := 9 output := twoSum(nums,target) fmt.Println(output) }
解题二
多种思路解 :
package main import ( "sort" "fmt" "sync" ) var ( nums = []int{2,15} noSolu = []int{-1,-1} target = 26 wg sync.WaitGroup ) type Num struct { num,index int } type Nums []Num func (slice Nums) Len() int { return len(slice) } func (slice Nums) Less(i,j int) bool { return slice[i].num < slice[j].num } func (slice Nums) Swap(i,j int) { slice[i],slice[j] = slice[j],slice[i] } // 普通暴力 O(N^2) func algo1() []int { size := len(nums) for i := 0; i < size; i++ { for j := i + 1; j < size; j++ { if nums[i] + nums[j] == target { return []int{i,j} } } } return noSolu } // O(N^2) 优化 func algo2() []int { size := len(nums) mapped := make(Nums,size) for i,k := range nums { mapped[i] = Num{k,i} } sort.Sort(mapped) // 以上如果已经排好序则不需要 for i := 0; i < size; i++ { for j := i + 1; j < size && mapped[i].num + mapped[j].num <= target; j++ { if mapped[i].num + mapped[j].num == target { return []int{mapped[i].index,mapped[j].index} } } } return noSolu } // O(NlogN) 算法 func algo3() []int { size := len(nums) mapped := make(Nums,i} } sort.Sort(mapped) // 以上如果已经排好序则不需要 for _,k := range mapped { ret := sort.Search(size,func(j int) bool { return mapped[j].num >= target - k.num }) if ret != size { return []int{k.index,mapped[ret].index} } } return noSolu } // O(1) 算法(滑稽 func algo4() (ret []int){ ret = noSolu size := len(nums) wg.Add((size - 1) * size / 2) for i := 0; i < size; i++ { for j := i + 1; j < size; j++ { go func(i,j int) { if nums[i] + nums[j] == target { ret = []int{i,j} } wg.Done() }(i,j) } } wg.Wait() return } func main() { fmt.Println(algo1()) fmt.Println(algo2()) fmt.Println(algo3()) fmt.Println(algo4()) }