[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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

思路：

题目要求的是a+b+c=0，问题可以推广到a+b+c=target。3sum问题可以转化为2sum问题：对于任意一个A[i]，在数组中的其他数中解2sum问题，目标为target-A[i]。与2sum那题不同，这题要求返回的不是index而是数字本身，并且解不唯一。同时要求解排序并去重。

对排序来说，2sum中的双指针法更为方便，因为算法本身就用到排序。双指针排序法本身会去除一些重复的可能性：

(1, 2, 3, 4), target = 6
在扫描1时，解(2, 3, 4)的2sum = 5问题，找到一个解(1, 2, 3)。
在扫描2时，应当只对后面的数解2sum问题，即对(3, 4)解2sum = 4问题。这样避免再次重复找到解(1, 2, 3)。

但当存在重复数字时，光靠排序仍然无法去重：

(1, 2, 2, 2, 3, 4), target = 9
扫描第一个2时，解(2, 2, 3, 4)中的2sum=7问题，得到解(2, 3, 4)
扫描第二个2时，解(2, 3, 4)中的2sum=7问题，仍然会得到(2, 3, 4)

去除因重复数字而造成重复解有两个办法，一是将结果存到一个hash table中。由于STL的hash table (unordered_set, unordered_map)并不能为vector类型，除非自己提供一个hash function，颇为不便，也增加额外存储空间。而另一种方法就是在扫描数组时跳过重复的数字。上例中，只扫描1, 2, 3, 4来求相应的2sum问题。进一步简化，可以只扫描1, 2。因为3已经是倒数第二个数字，不可能有以它为最小数字的解。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { return threeSumGen(num, 0); } vector<vector<int> > threeSumGen(vector<int> &num, int target) { vector<vector<int>> allSol; if(num.size()<3) return allSol; sort(num.begin(),num.end()); for(int i=0; i<num.size()-2; i++) { if(i>0 && num[i]==num[i-1]) continue; int left=i+1, right=num.size()-1; while(left<right) { int curSum = num[left]+num[right]; int curTarget = target-num[i]; if(curSum==curTarget) { vector<int> sol; sol.push_back(num[i]); sol.push_back(num[left]); sol.push_back(num[right]); allSol.push_back(sol); left++; right--; while(num[left]==num[left-1]) left++; while(num[right]==num[right+1]) right--; } else if(curSum<curTarget) left++; else right--; } } return allSol; } };

总结：

这题原理上并不难，但要正确做好去重，还是要注意不少细节。红色部分的代码即为去重部分。ln 12为扫描时候的去重，ln 23-26为2sum时的去重。