# Go语言性能优化-两数之和算法性能研究

## 承题

1. 暴力法，循环迭代找出来，时间复杂度O(n^2),空间复杂度是O(1)
2. 一遍哈希表,时间和空间复杂度都是O(n)

## 暴力法

```func TwoSum1(nums []int, target int) []int {

n:=len(nums)

for i,v:=range nums {
for j:=i+1;j<n;j++ {
if v+nums[j] == target {
return []int{i,j}
}
}
}

return nil
}```

## 哈希法

Go语言里有map类型，这个默认的Hash实现，基于这个我们用Golang实现哈希法。

```func TwoSum2(nums []int, target int) []int {

m:=make(map[int]int,len(nums))

for i,v:=range nums {
sub:=target-v
if j,ok:=m[sub];ok{
return []int{j,i}
}else{
m[v]=i
}
}

return nil
}```

## 测试

```package main

import (
"flysnow.org/hello/lib"
"fmt"
)

func main(){
r1:=lib.TwoSum1([]int{2, 7, 11, 15},9)
fmt.Println(r1)
r2:=lib.TwoSum2([]int{2, 7, 11, 15},9)
fmt.Println(r2)
}```

```[0 1]
[0 1]```

## 性能期望

```func BenchmarkTwoSum1(b *testing.B) {
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum1([]int{2, 7, 11, 15},9)
}
}

func BenchmarkTwoSum2(b *testing.B) {
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum2([]int{2, 7, 11, 15},9)
}
}```

```pkg: flysnow.org/hello/lib
BenchmarkTwoSum1-8      50000000    26.9 ns/op  16 B/op   1 allocs/op
BenchmarkTwoSum2-8      20000000    73.9 ns/op  16 B/op   1 allocs/op```

## 数组位置调整

```BenchmarkTwoSum1-8      50000000    29.1 ns/op  16 B/op     1 allocs/op
BenchmarkTwoSum2-8      10000000    140 ns/op   16 B/op     1 allocs/op```

## 扩大数组个数

```const N  = 10

func BenchmarkTwoSum1(b *testing.B) {
nums:=[]int{}
for i:=0;i<N;i++{
nums=append(nums,rand.Int())
}
nums=append( nums,7,2)

b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum1(nums,9)
}
}

func BenchmarkTwoSum2(b *testing.B) {
nums:=[]int{}
for i:=0;i<N;i++{
nums=append(nums,rand.Int())
}
nums=append( nums,7,2)

b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum2(nums,9)
}
}```

```BenchmarkTwoSum1-8      20000000    73.3 ns/op  16 B/op     1 allocs/op
BenchmarkTwoSum2-8       2000000    660 ns/op   318 B/op    2 allocs/op```

10个元素是，暴力法比哈希法的性能快10倍。

```BenchmarkTwoSum1-8       2000000    984 ns/op   16 B/op     1 allocs/op
BenchmarkTwoSum2-8        500000    3200 ns/op  1451 B/op   6 allocs/op```

```BenchmarkTwoSum1-8      100     21685955 ns/op      16 B/op         1 allocs/op
BenchmarkTwoSum2-8      2000    641821 ns/op        322237 B/op     12 allocs/op```

138 篇文章34 人订阅

0 条评论

## 相关文章

### 0.30000000000000004

0.30000000000000004问题是计算机科学领域的经典BUG, 由比尔盖茨那一代人标准化的浮点数表示法造福了一代人也祸害了一代人, 由...

4173

3056

3414

### JS魔法堂：彻底理解0.1 + 0.2 === 0.30000000000000004的背后

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   一天有个朋友问我“JS中计算0.7 * 180怎么会等于125.9999999999...

3046

### 2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对...

3144

### Python中else关键字的常见用法

Python中的else常见用法有三：选择结构、循环结构和异常处理结构。 （1）选择结构 这应该是最常见的用法，与关键字if和elif组合来使用，用来说明条件不...

29710

2256

2483

1482

2859