15. 三数之和

三数值和
定义三个指针start,end,index。大循环为index，小循环为start去重：
一、对start和end的去重是碰到重复即进行start++或end—。
二、对index的去重并不能简单的index++,我看到有些题解这么做，跑了一遍后发现有bug会漏解。比如对数组[0,-1,-1,2]，index循环到第二个-1处时，直接跳过的话，会忽略[-1,-1,2]的解。我的处理是将start定位到index-1的位置，这样只需要对end指针进行移位来遍历所有情况

package main
import (
    "fmt"
    "sort"
)
func threeSum(nums []int) [][]int {
    // 排序
    sort.Ints(nums)
    var resultList [][]int
    var addSum int
    var index,left,right int
    for index=1;index<len(nums)-1;index++{
        left = 0
        right = len(nums)-1
        for left<index&&index<right{
            addSum = nums[left]+nums[index]+nums[right]
            if addSum ==0 {
                resultList = append(resultList,[]int{nums[left],nums[index],nums[right]})
                left++
                right--
            }else if addSum>0 {
                right--
            }else {
                left++
            }
        }
    }
    return resultList
}
func main() {
    fmt.Println(threeSum([]int{-1,0,1,2,-1,-4}))
    fmt.Println(threeSum([]int{0,0,0,0}))
}

这种会出现重复，难点在去重

package main
import (
    "fmt"
    "sort"
)
func threeSum(nums []int) [][]int {
    // 排序
    var res [][]int
    sort.Ints(nums)
    for i:=0;i<len(nums);i+=1{
        // 排序 可以去重 重复值没有必须在执行一遍了，也就做到了去重
        if i>0&&nums[i]==nums[i-1] {
            continue
        }
        l := i+1
        r := len(nums)-1
        for l<r{// 移动左右坐标点
            tmp := nums[i]+nums[l]+nums[r]
            if tmp ==0 {
                res = append(res,[]int{nums[i],nums[l],nums[r]})
                l+=1
                r-=1
                // 数字相同 去重
                for l<r&&nums[l]==nums[l-1] {
                    l+=1
                }
                for l<r&&nums[r]==nums[r+1] {
                    r-=1
                }
            }else if tmp>0 {// 如果和大说明需要取更小的值
                r-=1
            }else {// 如果和小于0 说明需要取更大的值
                l+=1
            }
        }
    }
    return res
}
func main() {
    fmt.Println(threeSum([]int{-1,0,1,2,-1,-4}))
    fmt.Println(threeSum([]int{0,0,0,0}))
    fmt.Println(threeSum([]int{-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0}))
}