关注、星标下方公众号，和你一起成长

作者 | 梁唐

出品 | 公众号：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。可以将复杂度优化到 。

更多细节参考代码：

classSolution{public:vector>threeSum(vector&nums){intn=nums.size();vector>ret;sort(nums.begin(),nums.end());for(inti=0;i0)break;//最左侧元素不重复枚举if(i>0&&nums[i]==nums[i-1])continue;unordered_setst;for(intj=i+1;ji+2&&nums[j]==nums[j-2])continue;inttarget=-nums[i]-nums[j];if(st.count(target)){ret.push_back({nums[i],nums[j],target});st.erase(target);}st.insert(nums[j]);}}returnret;}};

另一种思路

上面的做法本质上是枚举了第一个数，等于剩下的元素套用两数之和寻找答案。但其实元素排序，枚举了第一个数之后，我们也有其他的方法寻找答案，比如说如果熟悉两指针的话，也可以使用两指针来寻找元素组合。

因为所有元素有序，我们使用两个指针分别指向左右两个端点，如果和小于预期，那么将左侧指针向右移动。如果和大于预期，则将右侧指针往左移动。如果和刚好是目标，则算是找到了一个答案。但这不一定是唯一的答案，我们可以将左右指针都向内移动一位继续寻找。这样只需要依靠元素的有序性以及两指针的移动，就可以不依赖set寻找出所有的两数之和的组合。

其实之前的两数之和问题也可以这么操作，只不过相比于使用set的方法，相对不容易想到。并且复杂度要稍高一些。

classSolution{public:vector>threeSum(vector&nums){intn=nums.size();sort(nums.begin(),nums.end());vector>ret;for(inti=0;i0)break;if(i>0&&nums[i]==nums[i-1])continue;intl=i+1;intr=n-1;while(l0)r--;elsel++;}}returnret;}};

LeetCode中这题还能继续变形，从三数之和变成四数之和，这是LeetCode第18题。它的解法和思考的细节基本上本题类似，甚至直接枚举一个数，剩下的直接调用三数之和都可以通过，实在是没什么意思，就不展开赘述了，感兴趣的同学可以去试一试。

文章的内容就到这里，感谢大家的阅读，如果喜欢的话，恳请帮忙转发扩散。算法学习之旅，与你同行。

喜欢本文的话不要忘记三连~