目录：百日刷百题 刷题进大厂——Leetcode高频题精讲合集
上一篇：Leetcode 56. Merge Intervals 题解 | 下一篇：Leetcode 75. Sort Colors 题解
类别：Sort
题目：15. 3Sum
思路：
首先习惯性的，我们把题目描述画一画看，更有利于理解观察。
题目是找出三个数字的组合，使其和为0，这是一个典型的穷举组合问题。对于组合问题我们可以用树来表示。画一个根节点，每次按顺序取一个元素为第一层(L1)节点，因为组合是不需要考虑顺序的(可以思考一下如果是需要考虑顺序这里有什么不同？)，下一步我们只需要在所取节点的右边开始每次按顺序取一个元素为第二层(L2)节点，以此类推直至取到第n层节点(这里n=3)。在每次到达第三层的时候，我们计算一下sum是否为0，记录下为0的组合。那么基本框架就出来了从上图就出来了，我们只需要做一个递归调用，每次传入当前选取数字的index，然后循环取其后面的index进行下一层递归即可。
但是题目中并没有说给我们的数字是不重复(unique)的，也就是说可能会有这种输入条件：[1, -1, 1, -1, 1]。我们画一下看看。
看看圈出来的组合，只列举一部分组合就已经产生大量重复了。这些重复都是我们需要从结果集中去除的。这里有两种方法去重。一个是先找出所有目标组合，然后从这些组合中去重，另一种是在查找地过程中直接忽略掉重复组合。显然第二种方法可以减少大量无用计算工作，在重复值比较多的情况下计算量大大小于第一种。那么怎么在查找过程中去重呢？这里我们可以记住：排序并在枚举过程中忽略重复值。什么意思呢？比如上面那个列子，排完序后输入条件变成[-1, -1, -1, 1, 1]。我们在取完第一个-1后，同一层中忽略掉其它的-1，直接取1即可。如下图：
可以看到只要碰到红色情况(非本层第一个节点且跟前一个节点同值)即忽略此值，极大地减少了计算量。
总结一下我们的思路：首先排序数组，然后递归循环查找组合，并在组合中进行去重。
代码实现（Swift版本）：
复杂度分析：
第一个是排序(Line 4)，时间复杂度是O(NLog(N))，N为nums的长度。第二个是递归调用，我们既可以由题目是求组合直接得知时间复杂度是N^3，也可以分析估算。由于我们最多递归到第三层，观察前面的树形结构，假设最坏情况下N个不重复值，第一层共有N个节点，第二层为第一层每个节点下面对应的剩余个数，为(N-1),(N-2),(N-3)...0，共计N^2/2。第三层为第二层每个节点下面对应的剩余数值个数，为(N-2),(N-3),(N-3)...0 + (N-3),(N-4),(N-5)...0 + 0约等于N个N^2即N^3。所以最差情况下(无法剪枝)总的时间复杂度为O(N^3)。
这个时间复杂度在N比较大时很容易出现超时错误(Time Limit Exceeded)。我们明天来试试怎么进一步改进。