算法题也有升级版，两数之和的进阶问题——三数之和
算法题也有升级版，两数之和的进阶问题——三数之和
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
在上一篇文章当中，我们一起重温了LeetCode经典第一题。今天我们来看一道它的变形题：LeetCode15，三数之和。
我们来看题：
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
分析
从表面上来看这是第一题的简单拓展，从之前两个数变成了三个数。实际上这里面发生了很多变化，绝不是照搬之前一题的解法就可以搞定的。
从样例和题意中我们可以看出，比较麻烦的一点在于我们需要保证答案当中没有重复的三元组。而数据当中是有重复数字的，这样一来势必造成出现大量的重复结果。我们当然可以先寻找答案再进行去重，但考虑到复杂度，这是不可行的。比如极端情况下，所有数字全都是0时，会导致大量的重复。
所以我们就只有一条路了，在寻找答案的时候就需要保证答案是没有重复的。
在两数之和当中我们使用了map或者set，在那题当中我们只需要一重循环即可。但在本题当中，由于需要枚举三元组，即使是使用同样的方法，也需要两重循环。但是这依然不能处理重复的问题，需要额外的逻辑搞定。
不难发现，答案如果有重复，一定是因为多个相同的数字导致的。针对这个情况，我们可以使用排序的方法来解决。因为元素有序了之后，相等的元素都会排列在一起，比较方便判断。并且元素有序之后，通过下标的顺序就能知道元素的大小顺序，也能进行一些筛选。比如如果最左边的元素已经大于0了，一定无解。
另外中间和右侧的元素可以一样，但不能重复枚举。另外还需要注意，本题的时限卡得非常紧，
无法通过。所以我们不能使用set，而需要使用基于哈希表实现的unordered_set。可以将复杂度优化到
。
更多细节参考代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
// 最左侧元素大于0一定无解
if (nums[i] > 0) break;
// 最左侧元素不重复枚举
if (i > 0 && nums[i] == nums[i-1]) continue;
unordered_set<int> st;
for (int j = i+1; j < n; j++) {
// nums[j] != nums[j-2]，保证nums[j], target组合不会出现重复
if (j > i+2 && nums[j] == nums[j-2]) continue;
int target = - nums[i] - nums[j];
if (st.count(target)) {
ret.push_back({nums[i], nums[j], target});
st.erase(target);
}
st.insert(nums[j]);
}
}
return ret;
}
};
另一种思路
上面的做法本质上是枚举了第一个数，等于剩下的元素套用两数之和寻找答案。但其实元素排序，枚举了第一个数之后，我们也有其他的方法寻找答案，比如说如果熟悉两指针的话，也可以使用两指针来寻找元素组合。
因为所有元素有序，我们使用两个指针分别指向左右两个端点，如果和小于预期，那么将左侧指针向右移动。如果和大于预期，则将右侧指针往左移动。如果和刚好是目标，则算是找到了一个答案。但这不一定是唯一的答案，我们可以将左右指针都向内移动一位继续寻找。这样只需要依靠元素的有序性以及两指针的移动，就可以不依赖set寻找出所有的两数之和的组合。
其实之前的两数之和问题也可以这么操作，只不过相比于使用set的方法，相对不容易想到。并且复杂度要稍高一些。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
for(int i = 0; i < n-2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1;
int r = n-1;
while (l < r) {
int target = nums[i] + nums[l] + nums[r];
if (target == 0) {
ret.push_back({nums[i], nums[l], nums[r]});
l++; r--;
while (l < r && nums[l] == nums[l-1]) l++;
while (l < r && nums[r] == nums[r+1]) r--;
}else if (target > 0) r--;
else l++;
}
}
return ret;
}
};
LeetCode中这题还能继续变形，从三数之和变成四数之和，这是LeetCode第18题。它的解法和思考的细节基本上本题类似，甚至直接枚举一个数，剩下的直接调用三数之和都可以通过，实在是没什么意思，就不展开赘述了，感兴趣的同学可以去试一试。