15. 3Sum 三数相加

题目

给定一个整数数组 nums，找到所有的 i,j,k 游标，使得三个数相加等于 0。

解析

该问题借鉴 两数相加。我们首先要知道所有的两数相加之和，然后才能根据 map 来确定第三个数是否存在。

1. 我们划定一个 map[int]int 其 key 为数值，value 为坐标 i。
2. 用两个指针，一前一后，分别为 j，k 。首先 j=0，k=i+1 判断 nums[i] + nums[j] 取反是否在 map 中
3. 如果存在，是一种解法
4. 当 k 移动完成后，如果 i 值不存在 map，将 i 值写入 map 中。

一些复杂的情况：

1. 在判断 num[j] + num[k] 时，如何去除重复
   重复发生在两种情况中
   （1） j 固定不变时，第一次出现合适的值，后续出现相同的值
   （2） j 移动变化后，后续重复的问题

乱序去重代价过大。考虑对数组进行排序。

排序解析

排序后我们固定第一个数为 num[i]，然后在剩下数字两端分别为 num[j] num[k]
计算 num[i] + num[j] + num[k] 的关系。
如果相等，说明是一种解法，此时我们同时 j++ k--，如果解法和上一个相同，重复，继续步进
这里同时步进是没有问题的，因为两个数固定的话，另一个数要满足条件一定是固定的。

如果 num[i] + num[j]+num[k] < 0 ，移动 j，如果 > 0 移动 k
重复这个过程。

一些重复情况

1. [-1,0,0,1,1] 当 i = 0, j =1, k = 4 时，和为 0 此时，我们分别移动 j 和 k。但是 j 和 k 和以前的值一样，发生了重复，我们需要去除这个重复情况。即重复发生时 nums[j] == nums[j-1] && nums[k] = nums[k+1] 注意临界条件，j ！= i+1 && k != len(nums) -1
   为了书写代码方便，我们可以将逻辑转换为什么时候是不重复，可以作为结果。当sum 为 0 时。
   (1) 如果 j 位于左边界，一定不重复
   (2) 如果 k 位于右边界，一定不重复
   (3) 如果 nums[j] != nums[j-1] 一定不重复
   (4) 如果 nums[k] != nums[k+1] 一定不重复

if j == i+1 || k == len(nums)-1 || nums[j] != nums[j-1] || nums[k] != nums[k+1] {
  rst = append(rst,[]int{nums[i],nums[j],nums[k]})
}

2. [-1,-1,-1, 0,1]
   当 i = 0 时，我们得到 [-1,0,1] 此时，我们应该将 i 指针移动到下一个不等于 -1 的数，以避免后续再次匹配到相同的结果

for i<len(nums)-2
  if nums[i] == nums[i+1]
    i+=1

伪码

sort(nums)

for i=0; i< len(s); i++
  for j=i+1,k=len(s); j<k;
    sum = nums[i] + num[j] + nums[k]
    if sum == 0
      if notDup
        rst += {i,j,k}
    if sum < 0
        j++
    if sum > 0
        k--
   i = nextNotEqual(i)

代码

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var rst [][]int
    for i:=0; i<len(nums)-2; i++ {
        j:=i+1
        k:=len(nums)-1
        for ; j<k;{
            sum := nums[i]+nums[j]+nums[k]
            switch {
            case sum==0:
                if j == i+1 || k == len(nums)-1 || nums[j] != nums[j-1] || nums[k] != nums[k+1] {
                    rst = append(rst, []int{nums[i],nums[j],nums[k]})
                }
                j++
                k--
            case sum<0:
                j++
            case sum>0:
                k--
            }
        }
        if nums[i] > 0 {
            break
        }
        for ; i<len(nums)-2; {
            if nums[i] == nums[i+1] {
                i++
            } else {
                break
            }
        }
    }
    return rst
}