leecode two sum golang解析

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())
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!