原题链接

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

基本思路

思路1：暴力枚举，哈希去重，这题不好哈希，得自己手搓哈希函数，或者变成字符串哈希+分割字符串

思路2：从暴力枚举思想出发，先排序，变成有序数组，有序数组就能用双指针了，额外加一个枚举指针，变成三指针

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        // 不够三元组直接返回空
        if (nums.size() < 3) return res;
        // 先排序
        sort(nums.begin(), nums.end());
        // 首指针遍历
        for (int i = 0; i < nums.size(); ++i) {
            // 首指针去重，这里要接受重复数组的首元素，避免000的三元组被直接跳过
            if (i >= 1) if (nums[i] == nums[i - 1]) continue;
            // 剪枝：首指针指向元素大于0时，后面无需遍历
            if (nums[i] > 0) break;
            // 剩下双指针
            int l = i + 1, r = nums.size() - 1;
            while (l <  r) {
                if (nums[i] + nums[l] + nums[r] == 0) {
                    res.push_back({nums[i], nums[l], nums[r]});
                    // 同样，剩下双指针在接受首元素后去重
                    while (l + 1 < r && nums[l] == nums[l + 1]) ++l;
                    while (r - 1 > l && nums[r] == nums[r - 1]) --r;
                    ++l, --r;
                }
                else if (nums[i] + nums[l] + nums[r] < 0) ++l;
                else --r;
            }
        }
        return res;
    }
};