题解 | #三数之和#

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
       vector< vector<int> > res;
       int n = num.size();  //数组元素个数
       if(n < 3)
          return res;  //特判，元素不够3个的情况
       sort(num.begin(), num.end());  //先对数组元素进行排序
       for(int i = 0; i < n-2; i++){  //每轮将第0个到倒数第三个元素作为三元组的第一个元素
           if(i != 0 && num[i] == num[i-1])  //后两个元素相同时，无效
              continue;  //i+1继续验证
           int left = i+1, right = n-1;  //三元组首元素有效时，从其后面元素中找到左右边界
           int target = -num[i];  //用首元素的相反数来验证后两个数是否存在
           while(left < right){
               if(num[left] + num[right] == target){  //左右两数和为目标值时
                   res.push_back({num[i],num[left],num[right]}); //加入返回数组中
                   while(left + 1 < right && num[left] == num[left+1])
                       left++;   //左边有重复的数就跳过，
                   while(right - 1 > left && num[right] == num[right-1])
                       right--;   //右边有重复的数就跳过
                   right--, left++;   //更新左右边界，继续寻找下一对符合要求的元素
               }
               else if(num[left] + num[right] > target) 
                  right--;     //左右两值和更大时，右边界往左缩
               else            //左右两数和更小时，左边界往右移
                  left++;
           }
       }
       return res;
    }
};