package main
import (
"fmt"
"sort"
)
/*
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?
请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
*/
func main() {
fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
}
// 先做排序护理,方便去重
// 使用双指针遍历后部分剩余数组
func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
var res [][]int
for i, num := range nums {
if num > 0 {
break // 再往后三个正数不可能为0
}
// 第一层遍历数向前去重
if i > 0 && nums[i] == nums[i-1] {
continue
}
l, r := i+1, n-1
for l < r {
sum := num + nums[l] + nums[r]
switch {
case sum > 0:
r--
case sum < 0:
l++
default:
res = append(res, []int{num, nums[l], nums[r]})
// 第二层候选数向后去重
for l < r && nums[l] == nums[l+1] {
l++
}
for r > l && nums[r] == nums[r-1] {
l++
r--
}
l++
r--
}
}
}
return res
}