三数之和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: vectorvectorint threeSum(vectorint nums) { vectorvectorint ret; int n nums.size(); // 先排序便于后续去重 sort(nums.begin(), nums.end()); // 使用 set 去重避免重复三元组 setvectorint 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 那么后面的数都正数找不到一个负数和它相加为 03. 在该数字后面的区间按照双指针算法快速找到一个和为 -i 的数字。这样三者和为 0符合题目要求。双指针算法前提数组升序有序left左指针从数组最左端开始小数right右指针从数组最右端开始大数sumtarget当前两数之和过大。right 和 right 左边所有数字搭配总和都会大于 target所以right--减小大数sumtarget当前两数之和过小。left 和 left 右边所有数字搭配总和都会小于 target所以left增大小数sumtarget找到答案直接返回这两个数处理细节问题1.去重找到一种结果的时候left和right要跳过重复的元素当使用完一次双指针算法的时候i也需要去重去重的时候对于 left、right 以及 i也要避免越界2.不漏当找到一种结果的时候不要停缩小区间继续查找class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint ret; //排序 sort(nums.begin(),nums.end()); int n nums.size(); int target 0; //利用双指针解决问题 for(int a 0;an;)//固定数a { if(nums[a]0) break; int left a1,right n-1; target-nums[a]; while(leftright) { if(nums[left]nums[right] target) { left; } else if(nums[left]nums[right] target) { right--; } else { // 找到一组解 //{}自动生成vectorint的 ret.push_back({nums[a],nums[left],nums[right]}); left; right--; // 左指针去重避免越界 while(leftright nums[left]nums[left-1]) { left; } //右指针去重避免越界 while(leftright nums[right]nums[right1]) { right--; } } } //去重a a; while(an 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 时及时剪枝跳出循环。掌握这些细节就能写出既正确又高效的三数之和解法。