题目

题目解读

1.如果我们先固定一个数 a，问题就退化为在剩下的数中找 b + c = -a，这恰好是两数之和问题。
2.由于题目要求去重，且数组元素可能重复，使用排序 + 双指针会比哈希表更方便去重。

开始解题

一、排序法

        思路：

                排序：将数组从小到大排序，这样重复元素会相邻，便于跳过。同时可以利用有序性指导双指针移动。
                固定第一个数：遍历数组，将 nums[i] 作为 a。
                        如果 a > 0，由于数组已排序，后面的数都大于等于 a，三数之和不可能为 0，可以直接结束循环（剪枝优化）。
                双指针找另外两个数：在 i+1 到末尾的区间内，用 left 和 right 两个指针分别指向两端：
                        计算 sum = nums[left] + nums[right]。
                        如果 sum == target（target = -a），则找到一组解，加入结果。
                        如果 sum < target，说明需要更大的和，left++。
                        如果 sum > target，说明需要更小的和，right--。
                去重是关键：
                        外层去重：如果当前 a 和上一个 a 相同，跳过，否则会产生完全相同的三元组。
                        内层去重：找到一组解后，left 和 right 可能直接指向重复值，如果不跳过，会添加相同的三元组。所以需要将 left 一直右移到值变化，right 一直左移到值变化，然后再同时收缩一位。

        核心流程：

                1.对数组进行排序 Arrays.sort(nums)。
                2.初始化结果列表 List<List<Integer>> result。
                3.遍历 i 从 0 到 n-3：
                        如果 nums[i] > 0，直接 break（剪枝）。
                        如果 i > 0 且 nums[i] == nums[i-1]，continue（跳过重复 a）。
                        设置 left = i + 1，right = n - 1，target = -nums[i]。
                        当 left < right 时循环：
                                计算 sum = nums[left] + nums[right]。
                                如果 sum == target：
                                将 [nums[i], nums[left], nums[right]] 加入结果。
                                执行内层去重：
                                        用 while 循环将 left 移到下一个不同值的位置，将 right 移到上一个不同值的位置。
                                        然后 left++, right-- 继续寻找。
                                        如果 sum < target：left++。
                                        如果 sum > target：right--。
                4.返回结果列表。

        代码

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            // 剪枝：最小的数已经大于 0，三数之和不可能为 0
            if (nums[i] > 0) break;
            // 跳过重复的 a
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = n - 1;
            int target = -nums[i];

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 跳过重复的 b
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 跳过重复的 c
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    // 继续收缩
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。