1.题目 15. 三数之和
提示
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] nums[j] nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
代码语言：javascript复制输入：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：
代码语言：javascript复制输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
代码语言：javascript复制输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
2.解法（排序 双指针）：
算法思路：
本题与两数之和类似，是⾮常经典的⾯试题。
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和
那⾥⽤的双指针思想：【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品-CSDN博客
i. 先排序；ii. 然后固定⼀个数 a ：iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。但是要注意的是，这道题⾥⾯需要有「去重」操作i. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；ii. 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素。
3.代码实现
代码语言：javascript复制class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for (int i = 0; i < n;) // 固定数 a
{
if (nums[i] > 0)
break; // ⼩优化
int left = i 1, right = n - 1, target = -nums[i];
while (left < right) {
int sum = nums[left] nums[right];
if (sum > target)
right--;
else if (sum < target)
left ;
else {
ret.push_back({nums[i], nums[left], nums[right]});
left , right--;
// 去重操作 left 和 right
while (left < right && nums[left] == nums[left - 1])
left ;
while (left < right && nums[right] == nums[right 1])
right--;
}
}
// 去重 i
i ;
while (i < n && nums[i] == nums[i - 1])
i ;
}
return ret;
}
};
