#题解# 三数之和

利用互补的性质！！！

class Solution {
public:
  //  和两数之和一样，利用互补性质
    vector<vector<int> > threeSum(vector<int> &num) {
      int size = num.size();
      std::vector<std::vector<int>> res;
      
      if (size < 3) {
        return res;
      }
      
      std::sort(num.begin(), num.end());
      
      for (int i = 0; i < size; ++i) {
        if (i != 0 && num[i - 1] == num[i]) {
          continue;
        }
        
        int left = i + 1;
        int right = size - 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;
            }
            //  来到最后一个重复的数字
            ++left;
            --right;
          } else if (num[left] + num[right] > target) {
            --right;
          } else {
            ++left;
          }
        }
      }
      
      return res;
    }
};