题意

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]
]

给定一整型数组，从这个数组中找出三个数a b c并满足a+b+c=0，返回所有符合条件的组合，返回的组合不能有重复。（数组中每个元素不能重复使用）

思路1（TLE）

将公式转换为a+b=-c，先记数组中录每个整数的值到位置的映射map，再二重循环枚举另外两个数之和是否等于-c，并检查三个值分别来自不同的数，复杂度为O(n^2)。

但这种方法存在一个不足：当输入数组中存在大量等值的数时，只要有一个数能与另外两个数满足a+b+c=0，那么这些等值的数中的每一个将会形成一个结果，产生的这些结果都是无用的，额外浪费了时间，由于结果不能重复，额外的判重也浪费了时间，导致运行超时。

代码1（TLE）

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
37
38
39
40
41
42
class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
        vector<vector<int> > ret;
        map<int,int> M;
        set<vector<int> > S;
        for(int i=0;i<(int)nums.size();i++)
        {
            M.insert(make_pair(nums[i],i));
        }
        map<int,int>::iterator mit = M.begin();
        set<vector<int> >::iterator sit = S.begin();
        for(int i = 0;i<(int)nums.size(); i++)
        {
            for(int j = i;j<(int)nums.size(); j++)
            {
                if(i == j) continue;
                int sum = nums[i] + nums[j];
                mit = M.find(-sum);
                if(mit != M.end())
                {
                    if(mit->second != i && mit->second != j)
                    {
                        vector<int> v;
                        v.push_back(nums[i]);
                        v.push_back(nums[j]);
                        v.push_back(-sum);
                        sort(v.begin(),v.end());
                        sit = S.find(v);
                        if(sit == S.end())
                        {
                            ret.push_back(v);
                            S.insert(v);
                        }
                    }
                }
            }
        }
        return ret;
    }
};

思路2（AC）

现将给定的数组排序为升序（降序同理），并从小到大试图枚举a b c的值，在枚举时始终保证a<=b<=c，在确定a b后可以使用二分搜索寻找c，枚举每次找到新的a或b或c的值才进行判断，否则跳过。

简单证明：
1.由于a b c的相对位置不影响结果，最终的每一个结果总是可以用从小到大的三个值来描述，所以该算法能够覆盖所有情况。

2.由于数组有序，所以相同的a b c值总是接连出现，算法每次跳过与前次相同的a b c的值，所以该算法不会产生重复情况。

代码2（AC）

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int binsearch(vector<int>& nums,int left,int right,int key)
    {
        int mid;
        while(left < right)
        {
            mid = (left + right) / 2;
            if(nums[mid] < key)
            {
                left = mid + 1;
            }
            else if(nums[mid] > key)
            {
                right = mid;
            }
            else
            {
                return mid;
            }
        }
        if(nums[left] == key) return left;
        return -1;
    }
    vector<vector<int> > threeSum(vector<int>& nums) {
        vector<vector<int> > ret;
        sort(nums.begin(),nums.end());
        int len = nums.size();
        //find two digit equals target1 in range[i+1,len-1]
        for(int i = 0; i < len; i++)
        {
            int target1 = -nums[i];
            for(int j = i + 1; j < len - 1; j++)
            {
                int target2 = target1 - nums[j];
                int index = binsearch(nums, j + 1, len - 1, target2);
                if(index != -1)
                {
                    vector<int> v;
                    v.push_back(nums[i]);
                    v.push_back(nums[j]);
                    v.push_back(nums[index]);
                    ret.push_back(v);
                }
                while(nums[j+1] == nums[j]) j++;
            }
            while(nums[i+1] == nums[i]) i++;
        }
        return ret;
    }
};