双指针:
    时间复杂度O(n2)
    空间复杂度O(1)

    1. class Solution {
    2. public:
    3.     vector<vector<int>> threeSum(vector<int>& nums) {
    4.         vector<vector<int> > res;
    5.         // 首先将数组排序
    6.         sort(nums.begin(), nums.end());
    7.         // 然后有一层for循环，下标i从0开始，确定i的位置后
    8.         for (int i = 0; i < nums.size(); i++) {
    9.             // 如果i处元素大于0，那么后边的所有元素也都大于0，直接返回结果
    10.             if (nums[i] > 0) return res;
    11.             // 去重
    12.             if (i > 0 && nums[i] == nums[i-1]) continue;
    13.             // 将一个左指针定义在i+1的位置上，右指针定义在数组结尾的位置上
    14.             int l = i + 1, r = nums.size() - 1;
    15.             // 当两个指针未相遇时，进入while循环
    16.             while (l < r) {
    17.                 // 去重逻辑如果放在这，会导致l>=r，漏掉[0,0,0]三元组
    19.                 // 如果三个值加起来<0，左指针++，让三数之和大一些
    20.                 if (nums[i] + nums[l] + nums[r] < 0) {
    21.                     l++;
    22.                     // 如果三数之和>0，右指针--，让三数之和小一些
    23.                 } else if (nums[i] + nums[l] + nums[r] > 0) {
    24.                     r--;
    25.                     // 三数之和==0时，将三元组放入vector中
    26.                 } else {
    27.                     res.push_back(vector<int>{nums[i], nums[l], nums[r]});
    28.                     // 去重逻辑应该放在找到一个三元组之后
    29.                     while (l < r && nums[l] == nums[l+1]) l++;
    30.                     while (l < r && nums[r] == nums[r-1]) r--;
    31.                     l++;
    32.                     r--;
    33.                 }
    34.             }
    35.         }
    36.         return res;
    37.     }
    38. };