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
| func threeSum(nums []int) [][]int {
var ans [][]int
if len(nums) < 3 {
return ans
}
var nbs []int
var nb2s []int
cnt0 := 0
table := make(map[int]int)
for _, n := range nums {
if n == 0 {
cnt0++
}
_, has := table[n]
if has {
table[n]++
if table[n] == 2 {
nb2s = append(nb2s, n)
}
} else {
table[n] = 1
nbs = append(nbs, n)
}
}
if cnt0 > 2 {
ans = append(ans, []int{0, 0, 0})
}
for _, n1 := range nb2s {
if n1 == 0 {
continue
}
n2 := -2 * n1
_, ok2 := table[n2]
if ok2 {
ans = append(ans, []int{n1, n1, n2})
}
}
sort.Ints(nbs)
for i1 := 0; i1 < len(nbs)-1; i1++ {
n1 := nbs[i1]
if n1 > 0 {
break
}
for i2 := i1 + 1; i2 < len(nbs); i2++ {
n2 := nbs[i2]
if n1+n2 > 0 {
break
}
n3 := -n1 - n2
if n1 >= n3 || n2 >= n3 {
continue
}
_, ok := table[n3]
if ok {
ans = append(ans, []int{n1, n2, n3})
}
}
}
return ans
}
|