NOTES · 学习笔记

三数之和:排序 + 双指针 + 去重

LeetCode双指针 · 中等约 5 分钟

题目

题目:给定整数数组 nums,判断是否存在三元组满足 i、j、k 互不相同,且 nums[i]+nums[j]+nums[k]==0,返回所有和为 0 且不重复的三元组。示例:输入 nums = [-1,0,1,2,-1,-4],输出 [[-1,-1,2],[-1,0,1]]——注意输出的顺序和三元组内的顺序并不重要。

我们看思路:这道题要从一个数组中找到三个数字,相加等于 0,并且不能出现重复。所以我们这样想:先排序,nums 变成 [-4,-1,-1,0,1,2]。排好序后,定义一个 i,再定义一个 left 指针指向 i 后面一位的位置,再定义一个 right 指针指向最后元素的位置。

现在 i 指向 -4,left 指向 -1,right 指向 2。题目要求 i+left+right 等于 0,此时 i=-4,left+right=1,i+left+right<0 无法满足要求。当三个数的和小于 0 时,i 不动,让 left 右移寻找更大的数;只有当前 left 和 right 的搜索结束后,外层循环才会让 i 移动到下一个位置。

i 走到第二位元素 -1 的位置,left 来到第三位元素 -1,right 还是最后一位 2。此时 i+left+right=0 满足条件,输出 [-1,-1,2]。然后 i 走到第二个 -1 再算一遍,会再次得到 [-1,0,1]——和之前找到的答案重复了,所以必须考虑去重。

这道题还需要专门考虑去重的问题。首先是 i 的去重:因为数组已经排好序,相同的数字会挨在一起。如果当前的 nums[i] 和前一个 nums[i-1] 相同,说明我们已经用这个数字作为第一个数寻找过了,再寻找一次就可能得到重复的三元组,直接跳过当前的 i。然后是 left 和 right 的去重:找到答案后,left++ 和 right-- 还有可能出现相同答案,所以也要去重。

func threeSum(nums []int) [][]int {
    sort.Ints(nums) // 先将数组从小到大排序,方便后面使用双指针

    result := [][]int{} // 定义结果数组,用来保存最后找到的三元组

    // i 遍历数组,每次固定一个数
    for i := range nums {

        // 如果当前 nums[i] 和前一个数一样,说明这个数已经作为第一个数找过了
        // 所以直接跳过,避免出现重复的三元组
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // left 指向 i 后面的第一个位置
        left := i + 1

        // right 指向数组最后一个位置
        right := len(nums) - 1

        // 只要 left 还在 right 的左边,就继续寻找
        for left < right {

            // 计算三个数的总和
            sum := nums[i] + nums[left] + nums[right]

            if sum < 0 {
                // 总和小于 0,说明三个数加起来太小了
                // 数组已经排序,所以让 left 右移,找一个更大的数
                left++
            } else if sum > 0 {
                // 总和大于 0,说明三个数加起来太大了
                // 所以让 right 左移,找一个更小的数
                right--
            } else {
                // 总和等于 0,说明找到了一个符合要求的三元组
                result = append(result, []int{
                    nums[i],
                    nums[left],
                    nums[right],
                })

                // left 去重
                // 如果 left 后面还是相同的数字,就跳过去
                // 避免得到重复的三元组
                for left < right && nums[left] == nums[left+1] {
                    left++
                }

                // right 去重
                // 如果 right 前面还是相同的数字,就跳过去
                // 避免得到重复的三元组
                for left < right && nums[right] == nums[right-1] {
                    right--
                }

                // 找到答案后,两个指针继续向中间移动
                left++
                right--
            }
        }
    }

    // 返回所有找到的三元组
    return result
}