[LeetCode] 3Sum 解题报告

[题目] Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0 ? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is: [  [-1, 0, 1],  [-1, -1, 2] ]

[中文翻译] 给定n个整数的数组S，在S中是否存在三个元素a，b，c，使得a + b + c = 0 ？找到数组中所有和为零的不同的三元组。 注意：解决方案集不能包含重复的三元组。

例如， 给定数组S = [-1, 0, 1, 2, -1, -4]，

解集为： [  [-1, 0, 1],  [-1, -1, 2] ]

[解题思路] 朴素的算法，枚举a, b, c。O(n³)的效率，加上处理重复的组合，可能不止O(n³)。

考虑一个更简单的问题，2Sum，且数组是有序的（假设从小到大）。 朴素的算法枚举a, b，效率O(n²)。但其实，有很多情况我们是不需要枚举的。 例如数组A, B, C, D, E, F, G, H。如果A+H>0，那么B~G+H一定>0（因为数组是有序的）。如果A+H<0，那么A+B~G一定<0。如果A+H=0，那么A+B~G以及B~G+H要么与A, H重复，要么不等于零。因此，只需要从两边开始向中间遍历即可，根据A+H与0比较的情况，判断哪边需要往中间缩。这种思想和[LeetCode] Container With Most Water 解题报告 中的思想很像，都是根据一些性质排除那些不必要的枚举。该方法的效率为O(n)。

那么回到我们的3Sum问题，其实只需要先确定一个数c，然后问题就转换为了2Sum问题，不同的是原来的要求是a+b=0，因此A+H是与0去比较，现在是要求a+b=-c，因此A+H是与-c去比较。

代码实现地比较复杂，主要是在处理重复三元组的问题。因为最后结果集可能是n³的数量级，不能在获得结果集之后剔除重复三元组，这样的效率至少是O(n³logn)的。因此，需要在枚举的时候就排除枚举到重复的三元组。

[C++代码]