-
Notifications
You must be signed in to change notification settings - Fork 61
Expand file tree
/
Copy paththree_sum.go
More file actions
66 lines (59 loc) · 1.08 KB
/
three_sum.go
File metadata and controls
66 lines (59 loc) · 1.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main
import (
"sort"
)
//三数之和
//暴力求解
func threeSum1(nums []int) [][]int {
res := make([][]int, 0)
set := map[[3]int]bool{}
for i := 0; i < len(nums)-2; i++ {
for j := i + 1; j < len(nums)-1; j++ {
for k := j + 1; k < len(nums); k++ {
if nums[i]+nums[j] == -nums[k] {
lis := []int{nums[i], nums[j], nums[k]}
sort.Ints(lis)
var arr [3]int
copy(arr[:], lis)
if !set[arr] {
res = append(res, lis)
set[arr] = true
}
}
}
}
}
return res
}
//排序后，双指针解法
func threeSum2(nums []int) [][]int {
var res [][]int
sort.Ints(nums)
for i := 0; i < len(nums)-2; i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
j, k := i+1, len(nums)-1
for j < k {
if nums[j]+nums[k] == -nums[i] {
res = append(res, []int{nums[i], nums[j], nums[k]})
j++
k--
for j < k && nums[j] == nums[j-1] {
j++
}
for j < k && nums[k] == nums[k+1] {
k--
}
} else if nums[j]+nums[k] < -nums[i] {
j++
} else {
k--
}
}
}
return res
}