三数之和

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

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

示例 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⁵ <= nums[i] <= 10⁵

解题思路：

Q: 暴力三重循环时间复杂度是多少？
O(n³)，数据量大时超时。

Q: 两数之和的双指针做法，在有序数组里怎么移动指针？
和小于 target 则 left++，大于则 right--，等于则记录并同时移动，移动时跳过相同值去重。

Q: 排序后固定第一个数 nums[i]，剩下的问题变成什么？
两数之和，target 为 -nums[i]，左右指针从 [i+1, n-1] 两端收缩。

Q: 外层循环 i 怎么去重？nums[i] == nums[i-1] 时为什么跳过？
以相同值为第一个数找到的所有三元组必然重复，直接 continue。注意是和前一个比而不是后一个。

Q: 内层找到答案后，去重的 while 和 left++/right-- 的顺序？
先 while 跳过相同值，再 left++/right--。顺序不能反——反了跳过的是还没用的候选而非已用的。

整体思路：

排序后，外层枚举第一个数 nums[i]，内层用双指针在 [i+1, n-1] 找两数之和等于 -nums[i]。去重分两层：外层跳过与前一个相同的 nums[i]，内层找到答案后先跳过重复值再移动指针。整体 O(n²)。

C++

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    for (int i = 0; i < n - 2; i++) {
        int num = -nums[i];
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = n - 1;
        while (left < right) {
            if (nums[left] + nums[right] < num) left++;
            else if (nums[left] + nums[right] > num) right--;
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
}

时间复杂度 O(n²)，空间复杂度 O(1)。