三数之和（Three Sum）是算法面试中非常经典的一道题目，它考察了排序、双指针、去重与边界处理等多个核心知识点，几乎成为各大公司笔试和面试的高频考点。本文将从暴力枚举 + set 去重和排序 + 双指针两种解法入手，分别介绍它们的核心思想、实现细节与复杂度差异，帮助读者快速理解并掌握这道题的常见解题思路。
题目描述：
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
算法原理：
解法一：排序 + 暴力枚举 + set 去重
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; int n = nums.size(); // 先排序，便于后续去重 sort(nums.begin(), nums.end()); // 使用 set 去重，避免重复三元组 set<vector<int>> st; // 第一重循环：固定第一个数 i for (int i = 0; i < n; i++) { // 第二重循环：固定第二个数 j for (int j = i + 1; j < n; j++) { // 第三重循环：枚举第三个数 k for (int k = j + 1; k < n; k++) { // 判断三数之和是否为 0 if (nums[i] + nums[j] + nums[k] == 0) { // 将三元组放入 set 中自动去重 st.insert({nums[i], nums[j], nums[k]}); } } } } // 将 set 中的结果转为 vector 返回 for (auto& v : st) { ret.push_back(v); } return ret; } };解法二：排序+双指针
1.排序
2. 固定一个数 i，并且一个小优化为当枚举 i <= 0 的时候才固定它，如果 i > 0 那么后面的数都正数，找不到一个负数和它相加为 0
3. 在该数字后面的区间，按照双指针算法，快速找到一个和为 -i 的数字。这样三者和为 0，符合题目要求。
双指针算法：
前提：数组升序有序
left：左指针，从数组最左端开始（小数）
right：右指针，从数组最右端开始（大数）
sum>target：当前两数之和过大。right 和 right 左边所有数字搭配，总和都会大于 target，所以right--（减小大数）
sum<target：当前两数之和过小。left 和 left 右边所有数字搭配，总和都会小于 target，所以left++（增大小数）
sum=target：找到答案，直接返回这两个数
处理细节问题：
1.去重
找到一种结果的时候，left和right要跳过重复的元素
当使用完一次双指针算法的时候，i也需要去重
去重的时候，对于 left、right 以及 i，也要避免越界
2.不漏
当找到一种结果的时候不要停，缩小区间继续查找
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; //排序 sort(nums.begin(),nums.end()); int n =nums.size(); int target =0; //利用双指针解决问题 for(int a =0;a<n;)//固定数a { if(nums[a]>0) break; int left = a+1,right = n-1; target=-nums[a]; while(left<right) { if(nums[left]+nums[right] < target) { left++; } else if(nums[left]+nums[right] > target) { right--; } else { // 找到一组解 //{}自动生成vector<int>的 ret.push_back({nums[a],nums[left],nums[right]}); left++; right--; // 左指针去重+避免越界 while(left<right && nums[left]==nums[left-1]) { left++; } //右指针去重+避免越界 while(left<right && nums[right]==nums[right+1]) { right--; } } } //去重a a++; while(a<n && nums[a]==nums[a-1]) a++; } return ret; } };复杂度分析：
解法一：排序 + 暴力枚举 + set 去重
时间复杂度：O(n³)。排序需要 O(n log n)，三重循环枚举所有三元组需要 O(n³)，set 去重操作在常数时间内完成，因此整体时间复杂度为 O(n³)。
空间复杂度：O(n)。set 需要存储所有不重复的三元组，最坏情况下三元组的数量为 O(n²)，因此空间复杂度为 O(n²)。
解法二：排序 + 双指针
时间复杂度：O(n²)。排序需要 O(n log n)，外层循环固定一个数 i 需要 O(n)，内层双指针遍历剩余区间需要 O(n)，因此整体时间复杂度为 O(n²)。
空间复杂度：O(1)（不考虑返回结果所占用的空间）。双指针算法只需要常数级别的额外空间，不需要额外的数据结构来去重。
两种方法对比：
解法一（暴力枚举 + set 去重）实现简单、思路直观，但时间复杂度高达 O(n³)，在数据规模较大时性能较差；同时 set 去重需要额外的存储空间，空间复杂度为 O(n²)。
解法二（排序 + 双指针）通过排序和双指针技巧，将时间复杂度优化到 O(n²)，空间复杂度也降低到 O(1)，在时间和空间上都明显优于解法一。虽然实现稍复杂，但更适合处理大规模数据，是实际应用中更推荐的方案。
| 对比维度 | 解法一：排序 + 暴力枚举 + set 去重 | 解法二：排序 + 双指针 |
|---|---|---|
| 时间复杂度 | O(n³) | O(n²) |
| 空间复杂度 | O(n²) | O(1)（不考虑返回结果所占空间） |
| 实现难度 | 实现简单、思路直观，三重循环加 set 去重即可 | 实现稍复杂，需要理解双指针的移动规则和去重细节 |
| 适用场景 | 数据规模较小、对性能要求不高的场景 | 数据规模较大、追求高效性能的实际应用场景 |
选择建议：如果只是学习算法思路或处理小规模数据，解法一足够；但在实际工程和面试场景中，更推荐解法二，它在时间和空间上都明显更优，是更通用的方案。
易错点与边界条件
三数之和问题虽然思路清晰，但在实现过程中很容易踩到一些细节上的坑。下面总结几个最常见的错误，并给出对应的正确写法。
1. 去重时越界
在找到一组解之后，left 和 right 都需要跳过重复元素。如果跳过重复时没有判断 left < right，就可能出现越界访问，导致程序崩溃或产生错误结果。
// 错误写法：缺少 left < right 判断，可能越界 while (nums[left] == nums[left - 1]) { left++; } // 正确写法：先判断 left < right，再比较相邻元素 while (left < right && nums[left] == nums[left - 1]) { left++; } while (left < right && nums[right] == nums[right + 1]) { right--; }2. 遗漏重复三元组
找到一组解后，如果只移动 left 或只移动 right，而不是同时移动两个指针，就会漏掉其他可能的组合。正确做法是找到一组解后，left 和 right 同时向内收缩，再继续查找。
// 错误写法：只移动一个指针，可能遗漏其他解 left++; // 正确写法：找到一组解后，两个指针同时收缩 left++; right--;3. 固定 i 时未跳过重复值
外层循环固定 i 时，如果 i 与上一个值相同，会生成重复的三元组。因此每次处理完一个 i 后，需要跳过所有与它相等的值。
// 错误写法：没有跳过重复的 i，会产生重复三元组 a++; // 正确写法：跳过重复的 a，同时避免越界 a++; while (a < n && nums[a] == nums[a - 1]) { a++; }4. 遗漏 i > 0 的剪枝优化
数组排序后，如果当前固定的数 i 大于 0，那么它后面的数都为正数，不可能再找到和为 0 的三元组，此时应直接结束循环，避免无意义的计算。
// 正确写法：当 nums[a] > 0 时直接跳出循环 if (nums[a] > 0) { break; }掌握以上几个易错点，就能写出既正确又高效的三数之和解法。
总结
三数之和是一道非常经典的算法题，核心思路是：先对数组排序，再固定一个数，通过双指针在剩余区间内寻找另外两个数，使三者之和为 0。整个过程需要重点处理好去重和边界条件，才能保证结果既不重复也不遗漏。
两种解法各有适用场景：解法一（排序 + 暴力枚举 + set 去重）实现简单、思路直观，适合数据规模较小或仅用于学习算法思路的场景；解法二（排序 + 双指针）时间复杂度优化到 O(n²)、空间复杂度降低到 O(1)，更适合处理大规模数据，也是实际工程和面试中更推荐的方案。
面试中需要注意的关键点包括：去重时先判断 left < right 避免越界；找到一组解后 left 和 right 要同时收缩，避免遗漏其他组合；固定 i 时要跳过重复值；当 nums[a] > 0 时及时剪枝跳出循环。掌握这些细节，就能写出既正确又高效的三数之和解法。
