15 三数之和

2026年3月6日

一、题目

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

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

二、题解

思路： 排序 + 双指针。

先将数组排序，这样既能用双指针，又便于跳过重复元素。
外层遍历固定第一个数 nums[i]，在其右侧区间用 left、right 双指针向中间收缩寻找另外两个数。
计算 sum = nums[i] + nums[left] + nums[right]：sum == 0 记录答案；sum < 0 则 left++（增大）；sum > 0 则 right--（减小）。
去重：若 nums[i] 与前一个相同则跳过；找到答案后，left、right 也要跳过相邻的相同值。
剪枝：排序后若 nums[i] > 0，后面不可能凑出和为 0，直接结束。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        // 【核心前置步骤：排序】
        // 排序是双指针的前提，同时也让“跳过重复元素”变得极其简单（相同的数字肯定挨在一起）
        Arrays.sort(nums);

        // 遍历数组，每次“固定”一个数 nums[i]，然后在它后面的区间里用双指针找另外两个数
        for(int i = 0; i < nums.length; i++) {

            // 【极致剪枝】因为数组排过序，如果固定的第一个（最小的）数都已经大于 0 了，
            // 后面越加越大，绝对不可能凑出和为 0，直接打卡下班。
            if(nums[i] > 0) break;

            // 【第一重去重】如果当前的数跟上一个固定过的数长得一样，那就跳过，防止产生重复的结果。
            if(i > 0 && nums[i] == nums[i-1]) continue;

            // 【初始化双指针】left 在固定数的下一个位置，right 在数组最末尾
            int left = i + 1, right = nums.length - 1;

            // 只要左右指针没撞上，就一直往中间挤
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if(sum == 0){
                    // 找到了！存入结果
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 【第二重 & 第三重去重】重点！！！
                    // 既然已经记录过当前的 left 和 right 了，如果它们旁边的数跟它们一样，必须跨过去，不然又会出现重复组合。
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right] == nums[right-1]) right--;

                    // 去重完毕后，双指针同时往中间收缩一步，继续找在这个固定的 nums[i] 下，还有没有其他组合
                    left++;
                    right--;
                }
                // 如果加起来不够 0，说明数字太小了。因为数组是升序的，所以把 left 往右挪换个大点的数
                else if (sum < 0) {
                    left++;
                }
                // 如果加起来超过 0，说明数字太大了。把 right 往左挪换个小点的数
                else {
                    right--;
                }
            }
        }
        return ans;
    }
}

时间复杂度： $O(n^2)$ （排序 $O(n \log n)$ ，外层遍历 $O(n)$ ，内层双指针 $O(n)$ ，整体由 $O(n^2)$ 主导）

空间复杂度： $O(\log n)$ （排序所需的递归栈空间，结果数组不计入）

一、题目

二、题解

评论