LeetCode题目15：三数之和
LeetCode题目15：三数之和
原题描述
+
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
输入：[-1, 0, 1, 2, -1, 4]
输出：[[-1, 0, 1], [-1, -1, 2]]
原题链接：https://leetcode-cn.com/problems/3sum
思路解析
+
有印象的同学可能还记得，之前做过一道两数之和，思路还挺简单的。到了三数之和也别慌，至少三层循环暴力枚举是一定可以把这道题解出来的，但那样做就没什么意思了，我们还是思考有没有更优的思路吧~
假设在一个从小到大排好序的数组上做这道题，我们一定能够意识到一个基本事实：如果第 个数大于0，那么它没有任何机会和它后面的任意两个数相加为0，因为后面的数都是正数。
还是在排好序的数组上做这道题：如果第 个数不大于0，同时假设有另外两个可移动的指针分别放在了 之后，我们就假设是 和 ( )吧。有下面这么几种情况。
nums[i]+nums[j]+nums[k] > 0时，我们把 往左移是有机会让三个数之和向0靠近的。
反之，如果nums[i]+nums[j]+nums[k] < 0，我们右移 也是有机会让和向0靠近的。
所以我们只要固定一个 ，通过左右移动 和 就一定能够找到和为0的答案。但是去重是非常麻烦的，因为要分很多种情况讨论。
情况1——首先如果 和 的值相同，那么我们只需要其中选择一个位置继续搜索即可。因为后面 和 如果能和 配起来，那么也一定能和 配起来；
情况2——如果 和 的值相同，我们也能得到和情况1类似的结论；
情况3——如果 和 的值相同，同情况2。
所以碰到上面三种情况，直接跳过即可。所以这道题可以通过先排序，后用两个指针向中间不断移动的方法来解决。
复杂度分析
+
- 时间复杂度：
- 空间复杂度：
C++参考代码
+
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if (nums.size() < 3) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
if (nums[i] > 0) break;
else if (i > 0 && nums[i] == nums[i-1]) continue;
else {
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] == 0) {
res.push_back({nums[i], nums[l], nums[r]});
while (l < r && (nums[l] == nums[l + 1])) ++l;
while (l < r && (nums[r] == nums[r - 1])) --r;
++l; --r;
}
else if (nums[i] + nums[l] + nums[r] > 0) --r;
else ++l;
}
}
}
return res;
}
};腾讯云开发者
