https://leetcode.cn/problems/3sum/description/

重点是如何去重

<aside> 💡

整体解题思路：

1. 由于不要求返回下标，所以可以先对数组进行排序
   • 排序不仅利于搜索元素，也大幅节省了去重的工作量（相同的数会聚集在一起）
2. 使用双指针法。固定一个元素，在该元素之后与数组尾端各置一个指针，移动两个指针逐步判断与该固定元素的三数之和是否为0
   • 双指针思路有点类似209.长度最短的子数组，大了就缩右端，小了就缩左端 </aside>

<aside> 💡

去重思路重点：

1. 剪枝条件是nums[i] == nums[i+1]还是nums[i] == num[i-1]?
   • nums[i] == nums[i-1]表示如果当前值在之前已经使用过了则跳过，逻辑正确
   • nums[i] == nums[i+1]会影响到left指针的判断（left的初始值为i+1），逻辑错误
2. 双指针如何去重？何时去重？
   • 先记录结果再去重，先去重可能会导致诸如{0, 0, 0, 0}这样的数组丢失可行解（left和right都移动完了还没有完成去重）。 </aside>

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    // 先排序
    std::sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size(); ++i) {
        // nums[i] > 0时，三数之和一定大于0
        if (nums[i] > 0) {
            return ans;
        }

        // 对i去重
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        // 左右指针，一个指向i后，一个指向数组末尾
        int left = i + 1;
        int right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                --right;
            } else if(sum < 0){
                ++left;
            } else {
                ans.push_back({ nums[i], nums[left], nums[right] });
                // 对left与right去重
                while (left < right && nums[left + 1] == nums[left]) {
                    ++left;
                }
                while (left < right && nums[right - 1] == nums[right]) {
                    --right;
                }
                // 找到解后left与right同时向内收缩
                ++left;
                --right;
            }
        }
    }
    return ans;
}