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, 7, 11, 15}
fmt.Println(nums[0:])
target := 9
output := twoSum(nums, target)
fmt.Println(output)
}
解题二
多种思路解 :
package main
import (
"sort"
"fmt"
"sync"
)
var (
nums = []int{2, 7, 11, 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, size)
for i, k := range nums {
mapped[i] = Num{k, 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())
}
有疑问加站长微信联系(非本文作者)