题解 | #三数之和#

//参考了代码随想录15.三数之和的写法
//本题的思路是“三指针”，先对数组进行排序，排序后用遍历数组，指针i指向的就是数字a，指针i的下一个位置记为left，即数字b，然后再拿一个指针指向数组中的最后一个数字，即数字c。
//通过不断判断a+b+c与0的关系，比0大就让right左移，比0小就让left右移。通过这种方式不断收缩left与right，直到找到a+b+c=0为止，将其添加进列表里。当然，一个i中可能有多解，在这种情况下依然需要继续收缩left与right。也有可能没解，这样收缩到left==right时，就步进i。
//这题的一大难点在于“去重”。对a的去重时应该使用num[i]==num[i-1]，而不能使用num[i]==num[i+1]，避免某一对三元组还没被遍历过就先被排除掉了。比如[x,x,x,-1,-1,y,y,2]这种情况下，原本-1，-1，2可以构成一个三元组，但i刚指向第一个-1时就把该情况排除了，是不行的。
//对b和c的去重见代码中
#include <vector>
class Solution {
  public:

    vector<vector<int> > threeSum(vector<int>& num) {
        vector<vector<int> >result;
        if (num.size() < 3 ) //非法情况。
            return result;
        sort(num.begin(), num.end()); //对num进行排序。

        for (int i = 0; i < num.size(); i++) {
            if (num[i] >
                    0) //a大于0了，b和c在排序数组中也必然大于0，和不可能等于0
                break;
            if (i > 0 && num[i] == num[i - 1]) //对a去重。
                continue;
            int left = i + 1;
            int right = num.size() - 1;

            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组。很遗憾我一开始也是这么写的。
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (num[i] + num[left] + num[right] > 0) {
                    right--;
                } else if (num[i] + num[left] + num[right] < 0) {
                    left++;
                } else  {
                    result.push_back({num[i], num[left], num[right]});
                    while (right > left && num[right] == num[right - 1])right--;
                    while (right > left && num[left] == num[left + 1])left++;
                    right--;//如果只平移right，不平移left，却也能依然符合0的话，说明right在平移前后都是相同的值，是重复的了，所以还是都得平移。
                    left++;
                }

            }
        }
        return result;
    }
};