给你一个整数数组 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 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
核心题解：三数之和（排序 + 双指针法）
1. 算法核心思想：降维打击
如果是暴力解法，需要三个 for 循环穷举所有的三个数组合，时间复杂度是极其恐怖的 O(n3)。 为了优化，我们采用**“固定老大，双指针找小弟”**的策略，这是一种经典的降维打击：
- 提前给数组排序（这是双指针能生效的唯一绝对前提）。
- 用一层
for循环固定第一个数字（老大i）。 - 将寻找另外两个数字的任务，转化为一个在有序数组里寻找目标值
-nums[i]的**“两数之和”**问题。 - 使用一前（
front）一后（back）两个指针向中间靠拢，时间复杂度成功降维到 O(n2)。
2. 避坑指南：“去重”
这道题 80% 的报错都来自于“答案中包含重复的三元组”。我们在代码中必须布下三道防线：
- 防线一（极致剪枝）：如果排好序后，老大
nums[i]都已经大于 0 了，说明后面的数字全是正数，再怎么加也不可能等于 0，直接break提前下班。 - 防线二（老大去重）：如果当前的老大和上一个老大长得一样，说明这个老大的所有组合在上一轮已经全找过了。必须**“回头看”**（
nums[i] == nums[i-1]），如果是，直接continue跳过。绝对不能“往后看”，否则会把[-1, -1, 2]这种合法的答案误杀。 - 防线三（小弟去重）：当找到一组答案，或者和偏大/偏小时，指针移动的同时，必须用
while循环跨过所有连续相同的数字，避免重复判断。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
// 1. 灵魂前提：必须排序
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
// 防线一：如果最小的数都大于0，不可能凑成0了
if (nums[i] > 0) {
break;
}
// 防线二：老大去重（注意是回头看 i-1，防止误杀同伙）
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int front = i + 1;
int back = n - 1;
while (front < back) {
int sum = nums[i] + nums[front] + nums[back];
if (sum == 0) {
// 记录真实的数字，而不是下标
result.push_back({nums[i], nums[front], nums[back]});
// 找到答案后，左指针先往前走并去重
front++;
while (front < n && nums[front] == nums[front - 1]) {
front++;
}
// 注：极其巧妙的闭环！此时 front 变大了，下一轮 sum 必然 >0，
// 会自动触发下方的 else 分支，从而让 back 也去重并向左移动。
}
else if (sum < 0) {
// 和太小，左指针往右走（变大），并进行小弟去重
front++;
while (front < n && nums[front] == nums[front - 1]) {
front++;
}
}
else {
// 和太大，右指针往左走（变小），并进行小弟去重
back--;
while (back > front && nums[back] == nums[back + 1]) {
back--;
}
}
}
}
return result;
}
};
4. 复杂度剖析
- 时间复杂度：O(n2)。数组排序的时间复杂度是 O(nlogn)。外层遍历
i是 O(n)，内部的双指针front和back相向而行，最多也是遍历整个剩余数组，时间也是 O(n)。总体算下来是 O(n2)。 - 空间复杂度：O(1) 或 O**(logn)**。如果不看存储结果的
result数组，双指针本身只用了常数级的额外空间（O(1)）。但在 C++ 中，sort()函数底层通常会使用快速排序的变体，会占用额外的 O(logn) 的栈空间。