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為數組長度。

●　空間復雜度：不確定，取決于內部排序算法的具體實現。