LeetCode 15. 三数之和

◎

本节目标

排序后固定一个数，用相向双指针寻找另外两个数并系统去重。

这题把双指针解题框架扩展到组合枚举：排序提供单调性，去重保证每个三元组只出现一次。

查看原题

题意与约束

找出所有和为零且不重复的三元组。三元组中的元素来自不同下标，答案顺序不限，但集合中不能出现重复组合。

从枚举到排序双指针

三层枚举为 O(n³)。排序后固定 nums[i]，剩余问题是有序区间中寻找和为 -nums[i] 的两个数。若三数和偏小，左指针右移；偏大，右指针左移。命中后两端都跳过相同值，固定值 i 也跳过重复值。

循环中，当前 i 之前的相同固定值已经处理过；[left, right] 是当前固定值下还未排除的有序二元候选。单调性保证每次移动不会漏掉和为零的组合。

代码实现

源码先排序，再依次固定第一个值。命中三元组后同时收缩两端，并继续跳过重复端点。

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> answer;

        for (int i = 0; i < static_cast<int>(nums.size()); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = static_cast<int>(nums.size()) - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    answer.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 answer;
    }
};

Python

Python 3

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        answer: list[list[int]] = []

        for i, value in enumerate(nums):
            if i > 0 and value == nums[i - 1]:
                continue

            left = i + 1
            right = len(nums) - 1
            while left < right:
                total = value + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    answer.append([value, nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return answer

复杂度分析

• 时间复杂度：O(n²)，排序为 O(n log n)，外层与双指针搜索合计 O(n²)。
• 空间复杂度：O(1) 辅助空间（不计排序实现和答案集合）。

易错点

• 不跳过固定值重复项，会重复生成相同三元组。
• 命中后只移动一端，可能陷入重复值或生成重复答案。
• 在未排序数组上依据和移动指针，移动没有单调性依据。

模式迁移

固定若干元素、把剩余部分交给有序双指针，是 k 数之和的常用递归结构。需要原下标或不允许改动输入时，可排序值与下标的配对，而不能直接丢失位置信息。