forked from LockGit/Go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfour_sum.go
54 lines (51 loc) · 1.07 KB
/
four_sum.go
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
/**
* Created by GoLand.
* User: lock
* Date: 2018/8/18
* Time: 20:38
* 给定一个数组[a,b,c,d,e],一个target值,找出满足a+b+c+d==target的不重复集合
*/
package main
import (
"sort"
"fmt"
)
func main() {
list := [] int{1, 0, -1, 0, -2, 2, 3}
target := 0
sort.Ints(list)
length := len(list)
var res [] []int
for i := 0; i < length-3; i++ {
if i > 0 && list[i-1] == list[i] {
continue
}
for j := i + 1; j < length-2; j++ {
if j > i+1 && list[j-1] == list[j] {
continue
}
left := j + 1
right := length - 1
for left < right {
sum := list[i] + list[j] + list[left] + list[right]
if sum == target {
data := [] int{list[i], list[j], list[left], list[right]}
res = append(res, data)
left = left + 1
right = right - 1
for left < right && list[left] == list[left-1] {
left = left + 1
}
for left < right && list[right] == list[right+1] {
right = right - 1
}
} else if sum < target {
left = left + 1
} else {
right = right - 1
}
}
}
}
fmt.Println(res)
}