15. 三数之和

题目#

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

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

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路#

转化为两数之和进行运算

代码#

func threeSum(nums []int) [][]int {
    n := len(nums)
    ans := [][]int{}
    // 排序，由于这道题的重点不是排序，所以可以直接用现成的
    sort.Ints(nums)

    // a 表示第一个数，进行一个遍历
    for a := 0; a < n; a++ {
        // 跳过相同的数（要求不重复）
        if a > 0 && nums[a] == nums[a-1] {
            continue
        }

        // 将三数求和转换为两数求和的问题
        target := 0 - nums[a]

        // c 从最右侧出发
        c := n - 1

        // b 从 a 的下一个位置出发（左起）
        for b := a + 1; b < c; b++ {
            // 相同的就跳过
            if b > a+1 && nums[b] == nums[b-1] {
                continue
            }

            // b < c -> 遇到之后就相当于左右互换了，不需要继续运算
            // nums[b]+nums[c] > target ->
            // nums 经过了一次排序，左边小右边大，同时 b 的移动是在第二个循环里，所以说只能动 c
            // 当二者之和大于所求数时，我们就可以通过减小c来使二者之和更靠近 target
            for b < c && nums[b]+nums[c] > target {
                c--
            }

            // 碰到了，相当于重复，直接跳出
            if b == c {
                break
            }

            // 如果两数求和的问题解出来了，就得到了三数问题的一个解，添加到解里边
            if nums[b]+nums[c] == target {
                ans = append(ans, []int{nums[a], nums[b], nums[c]})
            }

        }
    }

    return ans
}