15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

 

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

/*
  暴力破解法
      1. 先排序
      2. 3层循环遍历
      3. 去重--使用map
*/

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    check := make(map[string]bool)

    res :=make([][]int,0)
    
    for i:=0 ;i<len(nums);i++{
        for j:=i+1;j<len(nums);j++{
            for k:=j+1;k<len(nums);k++{
                if nums[i]+nums[j]+nums[k] == 0{
                    tmp :=fmt.Sprintf("%d%d%d", nums[i],nums[j],nums[k])
                    //check 去重
                    if _,ok:= check[tmp];!ok {
                        res= append(res,[]int{nums[i],nums[j],nums[k]})
                        check[tmp]=true
                    }
                }
            }
    } 
    return res
}

/*
  变种双指针
    1. 把3数之和为0 看做 两数之和等于指定数，这样就可以双指针遍历，把每个元素都做一次和，遍历
    2. 注意：
        1). 重复元素需要跳过，题目指定结果不能重复
        2). 
*/

func threeSum(nums []int) [][]int {
    sort.Ints(nums)

    res :=make([][]int,0)
    
    for i:=0 ; i<len(nums);i++{
        //非第一个位置的指定元素不能重复
        if i != 0 && nums[i-1] == nums[i]{     
            continue
        }

        left,right := i+1,len(nums)-1
        for left < right {
            //双指针遍历时，left不是初始位置，元素重复需要跳过，指针右移
            //eg：[-5,1,1,3,4] 下标 (0,1,4) &(0,2,4)都符合条件，但是数据重复 
            if left != i+1 && nums[left-1] == nums[left]{     
                 left++
                 continue
            }

            s := nums[i] + nums[left]+ nums[right]
            if s == 0 {
                res = append(res, []int{nums[i],nums[left],nums[right]})
                left++
            }else if s < 0{
                left++
            }else{
                right--
            }
        }
        
    }
   
    return res
}