[015] 三数之和 (3Sum)

难度：中等 | 标签：数组、双指针、排序

题目描述

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

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

解法：排序 + 双指针 (Sorting + Two Pointers) —— 推荐 ✅

这道题是“两数之和”的升级版。如果使用暴力解法，复杂度是，会超时。最优解法是先排序，然后固定一个数，再用双指针找另外两个数。

核心步骤

排序：将数组从小到大排序，这是使用双指针的前提，也方便去重。
遍历：固定指针 i 从 0 遍历到 n-2。
双指针：
- 令 left = i + 1, right = n - 1。
- 当 sum > 0，说明右边太大，right--。
- 当 sum < 0，说明左边太小，left++。
- 当 sum == 0，记录结果，并同时收缩 left 和 right。

代码实现 (C++)

cpp

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 1. 排序
        vector<vector<int>> res;
        int n = nums.size();
        
        for(int i = 0; i < n; i++) {
            // 剪枝优化：如果当前数字已经大于0，因为已经排序，后面不可能凑出0了
            if(nums[i] > 0) break; 
            
            // 去重关键点 1：跳过重复的基准数
            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) {
                    res.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    
                    // 去重关键点 2：跳过重复的左指针
                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    // 去重关键点 3：跳过重复的右指针
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
                else if(sum < 0) {
                    left++;
                }
                else {
                    right--;
                }
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：排序消耗，双指针遍历消耗，总体为。
空间复杂度：除了存储结果的 res 数组外，我们只使用了常数个变量。（忽略排序可能使用的栈空间）。

深度解析：为什么要用“三指针”？

很多同学能背下来代码，但面试时被问到“为什么不暴力破解”或“为什么不用哈希表”时容易卡壳。这里有两个核心逻辑：

1. 降维思想 (Dimensionality Reduction)

如果直接暴力求解，我们需要三层循环 for i, for j, for k，时间复杂度是，这在数据量较大时（如）会直接超时。我们的策略是：先固定一个数。

一旦固定了 nums[i]，问题就变成了：“在剩下的数组中，找到两个数，让它们的和等于 -nums[i]”。
这就成功把“三数之和”降维变成了“两数之和”。

2. 为什么是“排序 + 双指针”而不是“哈希表”？

在“两数之和”中，我们通常用哈希表来实现。但在这道题中，题目要求**“不可以包含重复的三元组”**。

哈希表的劣势：哈希表虽然快，但处理去重非常麻烦（需要对结果排序再存入 Set 去重），空间复杂度高且代码极易出错。
排序+双指针的优势：
1. 天然去重：因为数组有序，重复的元素挨在一起，我们只需要判断 nums[i] == nums[i-1] 就能轻松跳过重复值。
2. 利用单调性：
  - 数组有序意味着数据有方向性。
  - 如果 sum 太大，为了变小，只能 right--（往左移，找小一点的数）。
  - 如果 sum 太小，为了变大，只能 left++（往右移，找大一点的数）。
  - 这种方向确定的移动，保证了我们不用把所有组合都试一遍，从而将内层复杂度从降低到。

总结：外层循环内层双指针 = 总复杂度。这是本题在不使用额外大量空间前提下的理论下界。

易错点与核心考点

去重逻辑（Most Important）：
- i 的去重：必须是 if (i > 0 && nums[i] == nums[i-1])。
  - 错误写法：nums[i] == nums[i+1]。这样会漏掉 [-1, -1, 2] 这种结果，因为第一个 -1 会被跳过。我们要保留“第一个出现的”，跳过“后面重复的”。
- left/right 的去重：必须在找到一个解之后进行。
指针移动：
找到答案后，必须同时移动 left 和 right，并继续寻找下一组可能的解（因为可能存在多组解对应同一个 i）。
溢出风险：
虽然题目数据范围一般不会溢出 int，但在某些语言或极端情况下，nums[i] + nums[left] + nums[right] 可能会溢出，面试时可以顺口提一句“如果数据很大可以用 long long”。

[015] 三数之和 (3Sum) ​

题目描述 ​

解法：排序 + 双指针 (Sorting + Two Pointers) —— 推荐 ✅ ​

核心步骤 ​

代码实现 (C++) ​

复杂度分析 ​

深度解析：为什么要用“三指针”？ ​

1. 降维思想 (Dimensionality Reduction) ​

2. 为什么是“排序 + 双指针”而不是“哈希表”？ ​

易错点与核心考点 ​