题解 | #数组中相加和为0的三元组#

数组进行升序排序后，从左向右固定某一个数，left/right两个指针分别指向另外两个数，left指向最左端，right指向最右端，对三个数进行求和,如果小了就把left指针向右移，如果大了就把right指针向左移，如果和刚好是0则记录并且继续探索(left向右移且right向左移时可能存在多组解)，参考了Java的一个版本。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > rst;
        if(num.size() < 3)
        {
            return rst;
        }
        sort(num.begin(), num.end());
        for(int i=0;i<num.size()-2;i++)
        {
            if(num[i] > 0)
            {
                break;
            }
            if(i>0 && num[i]==num[i-1])
            {
                continue;
            }

            int left = i+1;
            int right = num.size() - 1;

            while(left < right)
            {
                int sum = num[i] + num[left] + num[right];
                if(sum > 0)
                {
                    //和超了，最右边指针向左移以获取较小的数;
                    right--;
                }else if(sum < 0)
                {
                    //和不够，最左边指针向右移以获取较大的数;
                    left++;
                }else
                {
                    //和刚好为0，但可能不止一组满足条件，左指针向右，右指针向左移时可能仍然满足条件;
                    vector<int> tmp;
                    tmp.push_back(num[i]);
                    tmp.push_back(num[left]);
                    tmp.push_back(num[right]);
                    rst.push_back(tmp);

                    //继续看是否还有满足条件的;
                    //左指针跳过重复数字;
                    while(left < right && num[left]==num[left+1])
                    {
                        left++;
                    }
                    //右指针跳过重复数字;
                    while(left < right && num[right] == num[right-1])
                    {
                        right--;
                    }

                    left++;
                    right--;
                }
            }
        }
        return rst;
    }
};