15. 3Sum

题目描述：给定一个有n个整数的数组S，找到其中所有由三个数a、b、c组成，使得a + b + c = 0的三元组。如：

given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1], [-1, -1, 2]
]

分析：3个数的和为定值，三重循环肯定可以解决，但复杂度太高。可以先排序，然后在一遍遍历中两边夹。时间复杂度O(n^2)，空间O(1)。这个思路可推广到k-sum，都是先排序，然后 k - 2 层循环，最里面再加层左右夹逼的循环，复杂度O( max{nlgn, n^(k - 1)} )。

代码：

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 ++ )          //因为目标值是0，所以每个三元组至少有一个负数，故只用遍历负数即可
        {
            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;
    }
};