题解 | #三数之和#

方法：双指针+排序

具体步骤：

• 对数组进行排序， 便于后续的查找
• 遍历数组，得到第一个数字后，将问题转换为寻找两个数字之和为第一个数字相反数的问题
• 其中要注意重复的数字要去除。

时间复杂度：o(n²)。排序需要o(logⁿ)，遍历需要o(n²)。

空间复杂度：o(1)

class Solution {
  public:
    vector<vector<int> > threeSum(vector<int>& num) {
        vector<vector<int> > res;
        int n = num.size();
        //特殊情况处理
        if (n < 3)
            return res;

        sort(num.begin(), num.end());

        for (int i = 0; i < n - 2; i++) {
            //重复的数字跳过
            if (i != 0 && num[i] == num[i - 1])
                continue;
            //两数之和为相反数
            int target = -1 * num[i];
            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                if (num[left] + num[right] == target) {
                    res.push_back({num[i], num[left], num[right]});
                    //去重
                    while(num[left] == num[left + 1] && left + 1 < right)
                        left++;
                    while(num[right] == num[right - 1] && left < right - 1)
                        right--;
                    //两个指针同时向内收缩
                    left++;
                    right--;
                } 
                else if(num[left] + num[right] < target)
                    left++;
                else
                    right--;
            }
        }

        return res;
    }
};