LeetCode15：三数之和（双指针问题） —— 题解
👋 欢迎阅读
🎯 欢迎来到「三数之和」题解之旅！本文将带你从“在数组中找出所有和为 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 = i+1，right = 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 + 1，right = 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]）：
外层i | nums[i] | target | 双指针过程 | 找到的三元组 |
|---|---|---|---|---|
| 0 | -4 | 4 | left=1(-1), right=5(2)，和=1<4，左移... 最终无解 | 无 |
| 1 | -1 | 1 | left=2(-1), right=5(2)，和=1 == target | [-1, -1, 2] |
| 2 | -1（跳过） | - | 跳过重复，不处理 | - |
| 3 | 0 | 0 | left=4(1), right=5(2)，和=3>0，右移... 最终[-1,0,1] | [-1, 0, 1] |
| 4 | 1（nums[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 + 1，right = n - 1。找到三元组后，先移动指针再跳过重复：
left++,right--；跳过
nums[left] == nums[left-1]和nums[right] == nums[right+1]。
外层循环结束时，跳过
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: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> 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]] vector<int> nums = {-1, 0, 1, 2, -1, -4}; Solution sol; vector<vector<int>> 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和right（left++;right--），再进行去重跳过。若先去重再移动，会导致left-1或right+1指向未处理的有效元素，可能跳过正确的组合。同时，去重时nums[left] == nums[left - 1]依赖于left已经自增，若忘记先自增，则left-1还是原来的left，会导致死循环。务必记住：先移动指针，再跳过重复值。
4.2for循环的迭代部分为空，容易忘记更新i
for (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最大为 3000，O(n²) 约 9e6，可以接受。如果数组长度扩大到10^5，这个算法是否还能运行？你能想到哪些优化思路？如果数组包含大量重复元素（例如
[0,0,0,...,0]），代码中的去重逻辑会如何影响性能？去重操作是否增加了额外开销？
📚延伸挑战
如果题目改为四数之和（返回所有和为 target 且不重复的四元组），你能基于三数之和的框架写出核心思路吗？
如果只要求判断是否存在一个三元组和为 0（不要求返回所有组合），代码可以如何简化？
如果你觉得本文对你有所帮助，欢迎：
👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路
📌深入思考答案
排序是双指针法的基础，它使得我们可以根据和的大小单调地移动指针，并且让重复元素相邻排列，从而便于去重。若不排序，去重需要借助哈希集合，复杂度会上升。
外层循环的
while(i < n-2 && nums[i] == nums[i-1])用于跳过固定元素重复的情况；内层双指针找到有效组合后的去重用于跳过左右指针指向的重复元素，两者共同保证三元组全局唯一。必须同时移动两端，因为当前组合已经满足条件，
left和right各自向内移动是唯一能产生新组合的方式；若只移动一端，会重复计算相同组合或导致死循环。n=10^5时 O(n²) 会超时，需考虑分治 + 哈希或剪枝优化，但三数之和问题本身在一般输入下 O(n²) 是经典最优解法。大量重复元素时去重循环会跳过大量无效候选，实际上加速了算法，虽然多了几次比较，但避免了向结果中加入重复三元组，整体性能更好。
🔍延伸挑战答案
挑战1：四数之和可以固定前两个数，对剩余区间使用双指针找两数之和，外层套两层循环，时间复杂度 O(n³)，去重逻辑扩展为两层循环各自跳过重复元素。
挑战2：只需判断是否存在，可大幅简化：排序 + 双指针，找到一组即返回
true，无需去重和收集所有结果，代码更简洁，时间复杂度仍为 O(n²)。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨