三数之和

最后更新：2024-05-09-22

链接：https://leetcode.cn/problems/3sum/description/

题目描述

给你一个整数数组 nums ，判断是否存在三元组 \([nums[i], nums[j], nums[k]]\) 满足 i != j、i != k 且 j != k ，同时还满足 \(nums[i] + nums[j] + nums[k] == 0\) 。请你返回所有和为 0 且不重复的三元组。

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

题目示例

示例 1：示例 2：示例 3：

输入： 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] 。
注意，输出的顺序和三元组的顺序并不重要。

输入： nums = [0,1,1]

输出： []

解释： 唯一可能的三元组和不为 0。

输入： nums = [0,0,0]

输出： [[0,0,0]]

解释： 唯一可能的三元组和为 0 。

提示：

• \(3 <= nums.length <= 3000\)
• \(-10^5 <= nums[i] <= 10^5\)

Go排序+双指针

type threeSumData struct {
    nums   []int
    n      int
    target int
    res    [][]int
    first  int
    second int
    third  int
}

func (t *threeSumData) threeSumWithFixC(target int) {
    // b取值得到了，取c的值，b在c的左侧，c肯定大于b的，c从后面往前去，因为排序了，所以正常情况，b+c>= target
    for t.second < t.third {
	    if t.nums[t.second]+t.nums[t.third] <= target {
		    break
	    }
	    t.third--
    }
}

// 固定A值，取B+C = target
func (t *threeSumData) threeSumWithFixB(target int) {
    t.third = t.n - 1
    for second := t.first + 1; second < t.n; second++ {
	    // 取一个b的值，去掉重复的
	    if second > t.first+1 && t.nums[second] == t.nums[second-1] {
		    continue
	    }

	    t.second = second
	    // fmt.Printf("second %v\n", second)
	    t.threeSumWithFixC(target)

	    // 如果指针重合，随着 b 后续的增加
	    // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
	    if t.second == t.third {
		    return
	    }

	    if t.nums[t.second]+t.nums[t.third] == target {
		    t.res = append(t.res, []int{t.nums[t.first], t.nums[t.second], t.nums[t.third]})
	    }
    }
}

func (t *threeSumData) threeSumWithFixA() {
    // 3 <= nums.length <= 3000
    // -10^5 <= nums[i] <= 10^5
    if t.n <= 2 {
	    return
    }

    // 数组排序
    sort.Ints(t.nums)

    // 取a值，
    for first := 0; first < t.n; first++ {
	    // 取一个a值，如果当前值与上一个值一样，则跳过
	    if first > 0 && t.nums[first] == t.nums[first-1] {
		    continue
	    }

	    // 已经取了a值，按照题目，a + b + c = target，那么剩余 b + c = target - a
	    t.first = first
	    remain := t.target - t.nums[first]
	    // fmt.Printf("first %v\n", first)
	    // a取值固定了，取b值，b在a值的后面
	    t.threeSumWithFixB(remain)
    }
}

func threeSum(nums []int) [][]int {
    data := &threeSumData{
	    nums:   nums,
	    n:      len(nums),
	    target: 0,
	    res:    make([][]int, 0),
	    first:  0,
	    second: 0,
	    third:  0,
    }
    data.threeSumWithFixA()
    return data.res
}