【15. 三数之和 中等】
题目：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
思路：
- 解法1：哈希解法
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。
大家可以尝试使用哈希法写一写，就知道其困难的程度了。 - 解法2：双指针法
其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
而且使用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。
接下来我来介绍另一个解法：双指针法，这道题目使用双指针法 要比哈希法高效一些，那么来讲解一下具体实现的思路。
- 首先对数组进行排序，排序后固定一个数 nums[i]，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
- 依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
- 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
- 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
- nums从小到大排序过，如果三数之和<0，left需要右移；如果三数之和>0，right需要左移
- 当 sum == 0 时，nums[left]== nums[left+1] 则会导致结果重复，应该跳过，left++
- 当 sum == 0 时，nums[right] == nums[right−1] 则会导致结果重复，应该跳过，right−−
动画效果如下：
代码：
- 解法1：哈希解法
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[j], c = -(a + b)for(int i = 0; i < nums.size(); i++) {if(nums[i] > 0) { //如果排序后第一个元素大于0，不可能形成三元组break;}// 三元组元素a去重if(i > 0 && nums[i] == nums[i - 1]) {continue; }unordered_set<int> set1;for(int j = i + 1; j < nums.size(); j++) {// 三元组元素b去重 // 为什么nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]?// 是因为当连续两个重复时，第一个数是b，第二个数是c，不用去重。连续三个重复时，要把第三个去掉。// 因为当连续两个重复时（即 nums[j] == nums[j - 1]），第一个数作为三元组中的b，而第二个数可以作为三元组中的c，不用去重。// 当连续三个重复时（即 nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]），第三个重复的元素在前两个元素已经考虑过的情况下，可以被跳过，因为不会形成新的三元组。if(j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {continue;}int c = 0 - (nums[i] + nums[j]);if(set1.find(c) != set1.end()) {result.push_back({nums[i], nums[j], c});set1.erase(c); // 三元组元素c去重}else {set1.insert(nums[j]);}}}return result;}
};
时间复杂度: O(n^2)
空间复杂度: O(n)，额外的 set 开销
- 解法2：双指针法
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[j], c = -(a + b)for(int i = 0; i < nums.size(); i++) {if(nums[i] > 0) { //如果排序后第一个元素大于0，不可能形成三元组break;}// 去重三元组元素aif(i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.size() - 1;while(left < right)// 去重复逻辑如果放在这里，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++;*/// nums从小到大排序过，如果三数之和<0，left需要右移；如果三数之和>0，right需要左移if (nums[i] + nums[left] + nums[right] < 0) left++;else if (nums[i] + nums[left] + nums[right] > 0) right--;else {result.push_back({nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;// 找到答案时，双指针同时收缩left++;right--;}}return result;}
};
时间复杂度: O(n^2)
空间复杂度: O(1)
总结：
去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]
如果要求返回的是索引下标， 就不能使用双指针法了，因为这里的双指针法一定要排序，一旦排序之后原数组的索引就被改变了。
参考：
代码随想录