三数之和 | Coder

题目描述

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

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

解题思路

如果只是单纯的三数之和，那么就是一道很简单的题，首先对数组进行排序，接着固定一个数，然后在剩下的数中查找有无两个数字与这个固定的数字加起来为 $0$，有则找到一对，使用双指针即可，具体可以参考两数之和。但是题目要求找到所有的不重复的三元组，这就使得题目有点不一样了。正是因为在这里耗费了大量的时间，我才决定将此题记录下来。

一开始我的想法就是先找到所有的三元组，然后去重。找到所有的三元组容易，但是去重难，一开始我想使用 Set 集合进行去重。但是因为每一个三元组都是一个 List 集合，去重比较的是地址值，所以直接添加 List 集合到 Set 集合中是无法去重。因此我产生了一个大胆的想法，因为它比较的是地址值，所以我想写一个类继承 List 类，然后重写它的 hashCode 与 equals 方法(我不知道 Set 是不是靠这两个判重的)，但是最后还是失败了。

后来我就去看题解，但是因为陷入了牛角尖，无法理解，觉得人家讲的不对，后来我就试图复现人家的代码，因为代码是根据别人的思路，但是按照自己的理解写的，所以写的不对，通过对比人家的代码，发现有一个地方写错了，这个地方正是我陷入误区的地方，所以通过纠正我就明白别人的算法，也就明白了如何去重。

算法去重的核心就是如果当前固定的数与上一个数相同，那么就跳过这个数。我一开始不理解的原因有两个：

没有意识到题目要求所有的三元组，而我之前的算法还是两数之和的逻辑，找到一个符合条件的三元组则结束，这就导致我没有意识到每一次都会找到所有与固定数有关的所有三元组，这就意味着下面那个数如果与它之前的数相同的话，它就没有查找的必要，否则就会重复。
另一个原因就是我看成了如果下一个数与当前数相同，则跳过当前数，直接来到下一个数，这个算法肯定是错的，怪自己没有看清

另一个有可能重复的情况，先举个例子，给定数组 [-1, 0, 0, 1, 1 ]，首先固定数 -1

此时我们找到了一个三元组 [-1, 0, 1] 使得三数之和为 $0$，但是因为要找到所有的三元组，所以要继续寻找

这时我们发现又找到一个三元组 [-1, 0, 1]，但是我们发现这个三元组与之前那个三元组重复了，其重复的原因就是 nums[start] == nums[start + 1] || nums[end] == nums[end - 1]，所以我们只要遇到上述情况直接跳过当前数，例如当 nums[start] == nums[start + 1] 的时候，直接 start++。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums.length < 3) {
            return results;
        }

        // 首先进行排序
        Arrays.sort(nums);

        
        for (int i = 0; i < nums.length; i++) {
            int target = nums[i];
            
            // 因为是升序，如果当前的数 > 0，说明后面的数全大于 0，不可能加起来为 0
            if (target > 0) {
                break;
            }
            // 不足三个数，break
            if (i + 2 >= nums.length) {
                break;
            }

            // 如果当前数与前一个数相同，防止重复，跳过
            if (i > 0 && nums[i - 1] == nums[i]) continue;

            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                if (nums[start] + nums[end] + target == 0) {
                    List<Integer> res = new ArrayList<>();
                    res.add(target);
                    res.add(nums[start]);
                    res.add(nums[end]);
                    results.add(res);

                    // 防止重复
                    while (start < end && nums[start] == nums[start + 1]) start++;
                    while (start < end && nums[end] == nums[end - 1]) end--;

                    start++;
                    end--;

                } else if (nums[start] + nums[end] + target < 0) {
                    start++;
                } else {
                    end--;
                }
            }
        }
        return results;
    }
}