-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path15. 3Sum.go
More file actions
46 lines (43 loc) · 845 Bytes
/
15. 3Sum.go
File metadata and controls
46 lines (43 loc) · 845 Bytes
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
package two_pointers
import "sort"
func threeSum(nums []int) [][]int {
// 排序
sort.Ints(nums)
// for 循环 + 快慢指针
res := make([][]int, 0)
for i := 0; i < len(nums); i++ {
if nums[i] > 0 { // nil
return res
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
// 快慢指针
slow := i + 1
fast := len(nums) - 1
// 0 - nums[i]
for fast > slow {
if nums[fast]+nums[slow]+nums[i] > 0 { // 左移
fast--
continue
}
if nums[fast]+nums[slow]+nums[i] < 0 { // 右移
slow++
continue
}
// 相等
res = append(res, []int{nums[i], nums[slow], nums[fast]})
// 去重
for fast > slow && nums[fast] == nums[fast-1] {
fast--
}
for fast > slow && nums[slow] == nums[slow+1] {
slow++
}
// 同时收缩 处于去重之后
fast--
slow++
}
}
return res
}