题目链接：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)

这道题的要求是在给定的正整数数组中，找到三个数，使其之和等于0。要求三个数字按照非递减排列，而且不包含重复的。

这道题的思路和之前的Two Sum差不多，简单方式是暴力查找，先排序，然后3层循环遍历数组，时间复杂度O(n3)。优化时，可以先固定一个数，再用两个指针l和r从这个数后面的两边往中间查找，当这三个数之和等于0的时候，记录一下，当之和大于0的时候，r左移，而当之和小于0的时候，l右移，直到l和r相遇。这个其实就是在Two Sum外层加1层循环，因此时间复杂度是排序的O(nlogn)加O(n2)，即O(n2)。

由于三个数字需要按照非递减序列排放，因此先排序可以满足此要求。又要求不包含重复元素，因此在选择第一个数字的时候以及后面两个指针查找时，需要跳过重复元素。

时间复杂度：O(n2)

空间复杂度：O(1)

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

class Solution
{
public:
    vector<vector<int> > threeSum(vector<int> &num)
    {
        vector<vector<int> > v;
        
        if(num.size() == 0)
            return v;
        
        sort(num.begin(), num.end());
        
        for(int i = 0; i < num.size() - 2 && num[i] <= 0; ++ i)
        {
            if(i > 0 && num[i] == num[i - 1]) // 跳过重复元素
                continue;
            
            int l = i + 1, r = num.size() - 1;
            while(l < r)
            {
                if(num[l] + num[r] == 0 - num[i])
                {
                    v.push_back({num[i], num[l], num[r]});
                    
                    while(++ l < r && num[l] == num[l - 1]); // 跳过重复元素
                    while(l < -- r && num[r] == num[r + 1]); // 跳过重复元素
                }
                else if(num[l] + num[r] > 0 - num[i])
                    -- r;
                else
                    ++ l;
            }
        }
        
        return v;
    }
};