欢迎阅读 欢迎来到「三数之和」题解之旅本文将带你从“在数组中找出所有和为 0 且不重复的三元组”这一经典面试题出发深入理解排序 双指针的通用套路并掌握如何避免重复解、高效剪枝在 O(n2)O(n2) 时间内完成搜索。在开始之前建议你先了解题目背景这是 LeetCode 15 题给定整数数组nums要求返回所有满足nums[i] nums[j] nums[k] 0的不重复三元组索引不同但值可能相同。暴力枚举 O(n3)O(n3) 不可行而排序 双指针可将复杂度降至 O(n2)O(n2)是解决此类问题的经典范式。明确学习目标掌握核心流程——先对数组升序排序然后固定一个数nums[i]在其右侧区间使用双指针left i1right n-1查找两数之和等于-nums[i]的组合。理解去重逻辑外层循环跳过重复的nums[i]内层找到目标后跳过重复的nums[left]和nums[right]。同时利用排序后的有序性双指针能根据和与目标的大小关系灵活移动快速收敛。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [-1,0,1,2,-1,-4]输出[[-1,-1,2],[-1,0,1]]。本文将从问题转化、排序 双指针策略设计、去重与剪枝技巧到代码实现层层递进。即使你对双指针还不熟悉我们也会从“固定一个数剩下两个数用双指针找”这一直觉出发让你轻松抓住核心思想——排序后利用有序性用双指针将三数之和转化为两数之和问题同时小心跳过重复值保证答案唯一。现在让我们一起在数组中找出所有和为 0 的不重复三元组吧 一.题目15. 三数之和 - 力扣LeetCode二.做题思路一、问题分析前置分析给定一个整数数组nums要求找出所有和为 0 且不重复的三元组。核心观察先将数组排序然后固定一个数问题转化为在剩余区间中找两数之和等于-nums[i]这正好可以用双指针解决。去重要求排序后跳过重复元素避免产生相同的三元组。二、算法策略排序 双指针第一步对数组进行升序排序。第二步外层循环固定第一个数nums[i]i从 0 到n-3若nums[i] 0则后面所有数都大于 0三数和不可能为 0直接结束循环优化。设置双指针left i 1right n - 1目标值target -nums[i]。第三步内层双指针查找计算sum nums[left] nums[right]若sum target则right--减小和若sum target则left增大和若sum target则找到一个三元组存入结果然后移动指针并跳过重复元素。第四步外层循环结束后跳过重复的nums[i]避免重复三元组。示例执行过程nums [-1, 0, 1, 2, -1, -4]排序后为[-4, -1, -1, 0, 1, 2]外层inums[i]target双指针过程找到的三元组0-44left1(-1), right5(2)和14左移... 最终无解无1-11left2(-1), right5(2)和1 target[-1, -1, 2]2-1跳过-跳过重复不处理-300left4(1), right5(2)和30右移... 最终[-1,0,1][-1, 0, 1]41nums[4]0跳出-结束-最终返回[[-1,-1,2], [-1,0,1]]与示例一致。三、正确性说明简单版本排序后外层固定一个数nums[i]将问题转化为在有序数组中找两数之和等于-nums[i]这是两数之和双指针法的标准应用。由于数组有序双指针能遍历所有可能的组合且不重不漏。去重机制跳过相邻相等元素确保每个三元组只被记录一次。若nums[i] 0则剩余元素均大于 0三数和必大于 0因此可提前结束不减正确性。该策略覆盖了所有和为 0 的三元组组合。四、实现细节边界防护先对nums排序时间复杂度 O(n log n)。外层循环for (int i 0; i n - 2; )注意i的更新在循环体内手动控制。内层双指针left i 1right n - 1。找到三元组后先移动指针再跳过重复left,right--跳过nums[left] nums[left-1]和nums[right] nums[right1]。外层循环结束时跳过nums[i] nums[i-1]。可加入剪枝若nums[i] 0直接break。时间复杂度 O(n²)空间复杂度 O(1)不考虑返回结果。五、返回值目标映射返回v即所有不重复的三元组每个三元组满足nums[i] nums[j] nums[k] 0。三.代码#include iostream #include vector #include algorithm using namespace std; class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint v; // 存储所有不重复的三元组 // 1. 排序便于使用双指针同时方便后续去重 sort(nums.begin(), nums.end()); int n nums.size(); // 2. 外层循环固定第一个数 nums[i] // 因为需要至少三个数所以 i 最大到 n-3 for (int i 0; i n - 2; ) { int left i 1; // 左指针指向第二个数 int right n - 1; // 右指针指向第三个数 int target -nums[i]; // 目标值另外两数之和应为 target因为 nums[i] 另外两数 0 // 内层双指针在 [left, right] 区间内查找两数之和等于 target while (left right) { int sum nums[left] nums[right]; // 如果当前和大于目标则右指针左移减小和 if (sum target) { right--; } // 如果当前和小于目标则左指针右移增大和 else if (sum target) { left; } // 找到一组符合条件的三元组 else { // 将当前三元组加入结果集 v.push_back({nums[i], nums[left], nums[right]}); // 移动指针继续寻找其他可能的组合 left; right--; // 去重跳过与刚刚使用的 left 相同的元素因为排序后相同元素相邻 while (left right nums[left] nums[left - 1]) { left; } // 去重跳过与刚刚使用的 right 相同的元素 while (left right nums[right] nums[right 1]) { right--; } } } // 外层循环的去重跳过与当前 nums[i] 相同的元素避免重复三元组 i; while (i n - 2 nums[i] nums[i - 1]) { i; } } // 返回所有不重复的三元组 return v; } }; int main() { // 测试用例包含重复元素期望输出 [[-1,-1,2], [-1,0,1]] vectorint nums {-1, 0, 1, 2, -1, -4}; Solution sol; vectorvectorint result sol.threeSum(nums); // 打印结果 for (auto triplet : result) { cout [; for (int i 0; i triplet.size(); i) { cout triplet[i]; if (i triplet.size() - 1) cout , ; } cout ] ; } cout endl; return 0; }四、易错点分析4.1 双指针去重时left和right的移动顺序v.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--; }易错原因找到一组解后必须先移动left和rightleft;right--再进行去重跳过。若先去重再移动会导致left-1或right1指向未处理的有效元素可能跳过正确的组合。同时去重时nums[left] nums[left - 1]依赖于left已经自增若忘记先自增则left-1还是原来的left会导致死循环。务必记住先移动指针再跳过重复值。4.2for循环的迭代部分为空容易忘记更新ifor (int i 0; i n - 2; ) { // ... i; while (i n - 2 nums[i] nums[i - 1]) { i; } }易错原因for循环的第三部分迭代语句为空i的更新完全依赖循环体末尾的手动操作。初学者容易在某个分支如找到解后忘记写i导致死循环i永远不变。另外去重while放在i之后如果i被误放在while之后或忘记写会导致i指向重复值而无法前进。必须确保每次循环结束时i都移动到下一个未处理的非重复元素否则外层循环无法正常终止。五、流程图 闭幕 恭喜你完成了「三数之和」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题要求不重复的三元组代码在排序后通过双指针固定一个数然后在剩余区间内寻找两数之和。请问为什么需要先排序如果不排序能否用同样的去重逻辑代码中在外层循环和找到有效三元组后都有去重逻辑如while(left right nums[left] nums[left - 1])。请解释这些去重操作分别在处理什么场景下的重复当sum target时代码在加入结果后同时移动left和right--然后再次去重。如果只移动一端会有什么问题本题的时间复杂度为 O(n²)排序 O(n log n) 双指针 O(n²)nums.length最大为 3000O(n²) 约 9e6可以接受。如果数组长度扩大到10^5这个算法是否还能运行你能想到哪些优化思路如果数组包含大量重复元素例如[0,0,0,...,0]代码中的去重逻辑会如何影响性能去重操作是否增加了额外开销延伸挑战如果题目改为四数之和返回所有和为 target 且不重复的四元组你能基于三数之和的框架写出核心思路吗如果只要求判断是否存在一个三元组和为 0不要求返回所有组合代码可以如何简化如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案排序是双指针法的基础它使得我们可以根据和的大小单调地移动指针并且让重复元素相邻排列从而便于去重。若不排序去重需要借助哈希集合复杂度会上升。外层循环的while(i n-2 nums[i] nums[i-1])用于跳过固定元素重复的情况内层双指针找到有效组合后的去重用于跳过左右指针指向的重复元素两者共同保证三元组全局唯一。必须同时移动两端因为当前组合已经满足条件left和right各自向内移动是唯一能产生新组合的方式若只移动一端会重复计算相同组合或导致死循环。n10^5时 O(n²) 会超时需考虑分治 哈希或剪枝优化但三数之和问题本身在一般输入下 O(n²) 是经典最优解法。大量重复元素时去重循环会跳过大量无效候选实际上加速了算法虽然多了几次比较但避免了向结果中加入重复三元组整体性能更好。延伸挑战答案挑战1四数之和可以固定前两个数对剩余区间使用双指针找两数之和外层套两层循环时间复杂度 O(n³)去重逻辑扩展为两层循环各自跳过重复元素。挑战2只需判断是否存在可大幅简化排序 双指针找到一组即返回true无需去重和收集所有结果代码更简洁时间复杂度仍为 O(n²)。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
