15. 3Sum-M

15. 三数之和

label : 数组、双指针

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

分析：

1. 暴力O(n^3)，超时
2. 先排序O(nlogN)，O(N^2),剩下那个元素用二分法找,超时
3. 排序+双指针，a=0,b=n-1,a->a++,b->b–,判断是否相等

/* 执行用时 :1436 ms, 在所有 Go 提交中击败了67.56%的用户 内存消耗 :99.3 MB, 在所有 Go 提交中击败了29.42%的用户 */
package mainimport ("fmt""sort"
)
type slice []int
func (s slice)Len()int{
    return len(s)
}
func (s slice)Swap(i,j int){
    s[i],s[j]=s[j],s[i]
}
func (s slice)Less(i,j int)bool{
    if s[i]<s[j]{
    return true}else{
    return false}
}
//sort+双指针,因为经过排序，所以可以直接过滤掉重复的
func threeSum(nums []int) [][]int {
    size:=len(nums)ret:=make([][]int,0)sort.Sort(slice(nums))for i:=0;i<size;i++{
    if i>0&&nums[i]==nums[i-1]{
     continue }for a,b:=i+1,size-1;a<b;{
    th:=0-nums[i]if nums[a]+nums[b]==th{
    ret=append(ret,[]int{
    nums[i],nums[a],nums[b]})for a<b&&nums[b]==nums[b-1]{
     b-=1 }for a<b&&nums[a]==nums[a+1] {
     a+=1 }a+=1;b-=1}else if nums[a]+nums[b]>th{
    for a<b&&nums[b]==nums[b-1]{
     b-=1 }b-=1}else{
    for a<b&&nums[a]==nums[a+1] {
     a += 1 }a+=1}}}return ret
}
func main() {
    tables:=[][]int{
    {
    -4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0},//[[-5,1,4],[-4,0,4],[-4,1,3],[-2,-2,4],[-2,1,1],[0,0,0]]{
    -1, 0, 1, 2, -1, -4},{
    0,0,0,0},{
    -4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6}, //[[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]}for i:=0;i<len(tables);i++{
    fmt.Println(threeSum(tables[i]))}
}