go的算法问题

Leetcode上的twosum算法怎么用go实现


*two Sum


Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
已邀请:

astaxie - 创造、获取、分享、传播和应用Go

赞同来自: ilmari themoonstone

package main

import (
"fmt"
)

func twoIndex(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 := twoIndex(nums, target)
fmt.Println(output)
}

SuperFashi - To code or be coded, that's a question.

赞同来自: astaxie Xanthus

写了四种算法:


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

chenqinghe - Gopher/PHPer

赞同来自: silentred

func twoSum(nums []int, target int) []int {
var m map[int]int
m = make(map[int]int)
for k, v := range nums {
m[v] = k
}
for k, v := range nums {
if _, ok := m[target-v]; ok {
if m[target-v] == k {
continue
} else {
return []int{k, m[target-v]}
}
}
}
return []int{}
}

今天刚好也做到了,话不多少,上代码!

astaxie - 创造、获取、分享、传播和应用Go

赞同来自:

麻烦把详细的问题copy过来,这个input和output的东西未必是真实的需求呢

ilmari

赞同来自:


  1. Two Sum QuestionEditorial Solution My Submissions


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.


Example:
Given nums = [2, 7, 11, 15], target = 9,


Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

ilmari

赞同来自:

不过看到其他语言为了减少时间复杂度,用了hashtable等方法,不知道golang里还有没有更优解

toukii

赞同来自:

package twosum

import (
"testing"
)

var (
input []int
filter map[int]Empty
)

func init() {
input = []int{2, 7, 11, 15}
filter = make(map[int]Empty)
}

type Empty struct{}

func twosum(in []int, target int) []int {
ret := make([]int, 0, 4)
mp := make(map[int]int)
for i, it := range in {
mp[it] = i
}
for i, it := range in {
k := target - it
if j, ok := mp[k]; ok {
ret = findOne(ret, i, j)
continue
}
if j, ok := mp[-k]; ok {
ret = findOne(ret, i, j)
continue
}
k = target + it
if j, ok := mp[k]; ok {
ret = findOne(ret, i, j)
continue
}
if j, ok := mp[-k]; ok {
ret = findOne(ret, i, j)
}
}
return ret
}

func findOne(ret []int, i, j int) []int {
if _, exist := filter[i]; exist {
return ret
}
ret = append(ret, []int{i, j}...)
filter[i] = Empty{}
filter[j] = Empty{}
return ret
}

func TestTwoSum(t *testing.T) {
ret := twosum(input, 9)
t.Log(ret)
}

SuperFashi - To code or be coded, that's a question.

赞同来自:

对了,楼上的 Map 也不失为一种好算法。因为使用 Golang 的 Map 实现是靠哈希实现的(pwwMap), 所以均摊 O(N)。当时忘了这件事,没写……

要回复问题请先登录注册