2.2　三数之和

题目描述（第15题）

给定一个包含n个整数的数组nums，判断nums中是否存在3个元素a、b、c，使a+b+c=0。找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如，给定数组 nums=[-1,0,1,2,-1,-4]，满足要求的三元组集合为[[-1,0,1]，[-1,-1,2]]。

题目的要求如下。

●　找到3个数相加等于0，而不是“两数之和”中的不定值target，因此本题相当于是个特例。

●　题目要求返回的是数本身，而不是索引值。

●　这道题存在多个答案，与上一题不同，本题要求返回所有可能的答案。

●　答案中不可以包含重复的三元组，所以需要考虑去重。

思路

由于这道题要求的不再是返回索引值，因此先排序，然后使用双指针的思路是可行的。具体算法是先对原数组进行一次排序，然后一层循环固定一个元素，循环内部利用双指针找出剩下的两个元素，这里要特别注意需要去重。上述算法除去排序部分的时间复杂度为O(n2)，相比之下排序过程不会成为性能瓶颈。

代码

复杂度分析

●　时间复杂度：上述代码for循环内部虽然有两个while循环，但是这两个while循环也仅仅会扫描一遍数组（最里面的while循环只是跳过一些重复的元素而已），因此总的时间复杂度仍然是O(n2)，而不是O(n3)，其中n为数组长度。

●　空间复杂度：不确定，取决于内部排序算法的具体实现。