15. 三数之和

题目

力扣题目

给定一个整数数组 nums，找出所有满足以下条件且互不重复的三元组：

其中三个下标必须互不相同。答案中不能包含重复三元组，输出顺序不作要求。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

考察内容

• 排序后使用相向双指针
• 根据三数之和移动左右边界
• 固定值与左右指针的分层去重
• 从三重枚举优化到 $O(n^2)$
• 提前结束条件

解题思路

排序 + 双指针

先将数组升序排序。随后枚举第一个数 nums[i]，剩余两个数在区间 [i + 1, n - 1] 中通过相向双指针寻找：

• left = i + 1
• right = n - 1

每轮计算：

因为数组已经有序：

• sum < 0：当前和太小，需要增大，执行 left++；
• sum > 0：当前和太大，需要减小，执行 right--；
• sum == 0：记录三元组，同时移动两个指针，并跳过相同值。

为什么可以提前结束

如果 nums[i] > 0，那么 nums[i] 以及它后面的元素都大于 0，三个数之和不可能再等于 0，可以直接结束外层循环。

不能在 nums[i] == 0 时结束，因为 [0,0,0] 是合法答案。

三层去重

题目要求的是不重复的数值组合，因此需要处理三个位置的重复：

1. 固定值去重：若 nums[i] == nums[i - 1]，相同的第一个数已经处理过，跳过当前 i；
2. 左指针去重：找到答案并移动 left 后，跳过与刚才左值相同的元素；
3. 右指针去重：找到答案并移动 right 后，跳过与刚才右值相同的元素。

固定值只能与前一个元素比较。如果错误地用 nums[i] == nums[i + 1] 去重，可能会漏掉 [-1,-1,2] 这种需要使用两个相同数值的合法三元组。

以排序后的数组 [-4,-1,-1,0,1,2] 为例：

• 固定 i = 1，nums[i] = -1；
• left = 2、right = 5，得到 -1 + -1 + 2 = 0；
• 记录 [-1,-1,2]，两端向内移动；
• 此时得到 -1 + 0 + 1 = 0，记录 [-1,0,1]；
• 下一个固定位置 i = 2 的值仍是 -1，直接跳过，避免重复结果。

复杂度

排序需要 $O(n\log n)$；外层枚举一个数，内层两个指针合计线性移动，因此主体需要 $O(n^2)$。整体复杂度为：

• 时间复杂度：$O(n^2)$
• 额外空间复杂度：忽略返回结果时为 $O(1)$；排序本身可能使用 $O(\log n)$ 的递归栈空间

代码演示

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());

    int n = static_cast<int>(nums.size());

    for (int i = 0; i < n - 2; ++i) {
        // 当前最小的数已经大于 0，后面不可能再凑出 0
        if (nums[i] > 0) {
            break;
        }

        // 对固定的第一个数去重
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left = i + 1;
        int right = n - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum < 0) {
                ++left;
            } else if (sum > 0) {
                --right;
            } else {
                result.push_back({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;
                }
            }
        }
    }

    return result;
}

易错点

• 忘记先排序：指针移动方向和相邻去重都依赖数组有序。
• 返回数组下标：本题要求返回三元组的值，不是元素下标。
• 固定值与后一个元素比较去重：会漏掉需要两个相同数值的答案，应与前一个固定值比较。
• 找到答案后只移动一个指针：应同时移动 left 和 right，再跳过两侧重复值。
• 去重时忘记 left < right：可能导致越界或无效访问。
• 在 nums[i] >= 0 时退出：nums[i] == 0 时仍可能存在 [0,0,0]，只能在 nums[i] > 0 时退出。
• 把本题写成普通两数之和哈希法后难以去重：哈希法可以求解，但组合去重和输出顺序处理更复杂；排序双指针更自然。

总结

三数之和可以拆成“枚举第一个数 + 在剩余有序区间中求两数之和”。排序让指针移动具有明确方向，也让重复值相邻，从而同时解决查找和去重问题。

真正需要掌握的是两点：

1. 和太小时移动左指针，和太大时移动右指针；
2. 固定值、左值和右值都要在正确的时机去重。

相关题目

• 1. 两数之和
• 16. 最接近的三数之和
• 18. 四数之和
• 167. 两数之和 II - 输入有序数组
• 454. 四数相加 II