题解 | #牛牛的三元组问题# | 哈希表

考虑到时间复杂度，这种题习惯性用哈希表来加速查找。

为了方便去重，哈希表的键值对应是：{ 数字：出现的位置 }

可以先枚举两个数的组合方式，然后利用

a + b + c = 0, c = 0 - a - b

找出 c

a 和 b 可以使用双指针进行枚举，因为是要求字典序排序，后面的数永远大于前面的数，所以第二个指针只用设置在第一个的后一位，不需要从0开始枚举

for (int i = 0; i < nums.size(); i++) {
  for (int j = i + 1; j < nums.size(); j++){
	int a = nums[i];
	int b = nums[j];
  }
}

但要考虑到重复枚举的情况，共有3种约束条件：

1. i > 0 时， nums[i - 1] != nums[i]
2. j > 1 时， nums[j - 1] != nums[j]
3. c 出现的位置应在 a 与 b 之后，即 index(c) > i && index(c) > j

#include <algorithm>
#include <cstddef>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > findTriplets(vector<int>& nums) {    
        // 字典序排序    
        sort(nums.begin(), nums.end());

        // 创建哈希表 { 数字: 出现的位置 }
        map<int, int> isExist;
        for (int i = 0; i < nums.size(); i++)
            isExist[nums[i]] = i;

        vector<vector<int>> ans;

        // 使用双指针枚举情况
        for (int i = 0; i < nums.size(); i++) {

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

            for (int j = i + 1; j < nums.size(); j++) {

                if (j > 1 && nums[j - 1] == nums[j])    // 去重
                    continue;

                int p = isExist[0 - nums[i] - nums[j]];
                if (p > i && p > j && p > 0)            // 防止重复组合
                    ans.push_back({ nums[i], nums[j], 0 - nums[i] - nums[j] });
            }
        }

        return ans;
    }
};