三数之和
    题目链接：https://leetcode-cn.com/problems/3sum/
    图片.png

    思路：排序+双指针，同时注意去重。固定指向最小数字的指针i

    • （剪枝）若nums[i] > 0，则直接结束
    • （去重）若nums[i] == nums[i - 1]，++i

    (i, nums.size())区间内双指针j, k在j < k的情况下遍历：

    • 若三数之和< 0，j++并跳过所有重复元素
    • 若三数之和>0，k—并跳过所有重复元素
    • 若三数之和=0， 存储该元组并j++ k—跳过所有重复元素

    参考代码

    1. class Solution {
    2. public:
    3.     vector<vector<int>> threeSum(vector<int>& nums) {
    4.         vector<vector<int>> res;
    5.         if (nums.size() < 3) {
    6.             return res;
    7.         }
    8.         sort(nums.begin(), nums.end());
    9.         for (int i = 0; i < nums.size() - 2; ++i) {
    10.            if (i > 0 && nums[i] == nums[i - 1]) {
    11.                continue;
    12.            }
    13.            if (nums[i] > 0) {
    14.                break;
    15.            }
    16.            int j = i + 1;
    17.            int k = nums.size() - 1;
    18.            while (j < k) {
    19.                 int s = nums[i] + nums[j] + nums[k];
    20.                 if (s < 0) {
    21.                     do {
    22.                         ++j;
    23.                     } while (j < k && nums[j] == nums[j - 1]);
    24.                 } 
    25.                 else if (s > 0) {
    26.                     do {
    27.                         --k;
    28.                     } while (j < k && nums[k] == nums[k + 1]);
    29.                 }
    30.                 else {
    31.                     vector<int> ans = {nums[i], nums[j], nums[k]};
    32.                     res.push_back(ans);
    33.                     do {
    34.                         ++j;
    35.                     } while (j < k && nums[j] == nums[j - 1]);
    36.                     do {
    37.                         --k;
    38.                     } while (j < k && nums[k] == nums[k + 1]);
    39.                 }
    40.             }
    41.         }
    42.         return res;
    43.     }
    44. };