一、题目描述
题目链接：三数之和
题目描述：
![给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i、j、k 互不相同，且 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。](https://i-blog.csdnimg.cn/direct/a674b1146a7547169123eeefce771bb5.png)
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [0,1,1]
输出：[]
示例 3：
输入：nums = [0,0,0]
输出：[]
提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
二、解题思路
三数之和问题可以基于两数之和的双指针思路进行扩展，核心是固定一个元素，将问题转化为两数之和。具体步骤如下：
- 排序预处理：对数组进行排序，为后续去重和双指针移动提供基础。
- 固定第三个元素：从数组末尾开始，依次固定一个元素
nums[i]，则问题转化为在[0, i-1]范围内寻找两个元素，使得它们的和为-nums[i]。 - 双指针搜索：在
[0, i-1]范围内使用左右双指针（left起始于 0，right起始于i-1），根据三数之和与 0 的大小关系移动指针：- 若和小于 0：左指针右移（增大总和）
- 若和大于 0：右指针左移（减小总和）
- 若和等于 0：记录三元组，并移动指针跳过重复元素
- 去重优化：在固定元素和移动双指针时，通过跳过重复值避免生成重复三元组。
三、代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序，为去重和双指针做准备
int size = nums.size();
vector<vector<int>> ret; // 存储结果
int i = size - 1; // 从末尾开始固定第三个元素
while (i >= 0) {
int left = 0, right = i - 1; // 双指针范围：[0, i-1]
while (left < right) {
int sum = nums[left] + nums[right] + nums[i];
if (sum < 0) {
left++; // 总和偏小，左指针右移增大总和
} else if (sum > 0) {
right--; // 总和偏大，右指针左移减小总和
} else {
// 找到符合条件的三元组
ret.push_back({nums[left], nums[right], nums[i]});
left++;
right--;
// 跳过左指针重复元素
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
// 跳过右指针重复元素
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
// 固定元素去重：跳过与当前i相同的元素
i--;
while (i >= 0 && nums[i + 1] == nums[i]) {
i--;
}
}
return ret;
}
};
四、越界问题深度分析
在三数之和的双指针实现中，越界风险主要集中在指针移动和数组访问的边界处理上，以下是关键分析：
1. 固定元素 i 的越界防护
- 初始值：
i从size-1开始（数组最后一个元素），确保nums[i]访问有效。 - 循环条件：
while (i >= 0)确保i不会小于 0，避免访问nums[-1]等无效索引。 - 去重逻辑：
while (i >= 0 && nums[i + 1] == nums[i])中，i >= 0是前置条件，防止i-1时i+1越界（例如i=0时i+1=1有效，但需确保i不小于 0 才能进入循环）。
2. 双指针 left 和 right 的越界防护
- 初始范围：
left从 0 开始，right从i-1开始，由于i >= 0，right初始值最大为size-2（当i=size-1时），确保nums[right]有效。 - 循环条件：
while (left < right)保证left始终在right左侧，避免两者交叉后访问无效索引（例如left = right + 1时的越界）。 - 去重逻辑：
while (left < right && nums[left] == nums[left - 1])中，left < right确保left不会超过右边界，left - 1 >= 0（因left初始为 0，且只有left++后才可能进入该循环，此时left >= 1）。while (left < right && nums[right] == nums[right + 1])中，right + 1 <= i-1 + 1 = i（因right初始为i-1），而i <= size-1，故right + 1 <= size-1，避免访问越界。
3. 总结：为何此代码不会越界？
- 所有数组访问（
nums[left]、nums[right]、nums[i]）的索引均通过循环条件和指针移动逻辑被限制在[0, size-1]范围内。 - 去重逻辑中的指针移动均有前置条件（如
left < right、i >= 0），防止指针超出有效范围。
五、去重逻辑解析
三数之和的核心难点之一是避免重复三元组，代码通过三层去重确保结果唯一：
固定元素去重：
- 当
nums[i]与nums[i+1]相同时，跳过当前i（i--），避免因固定相同元素导致重复三元组。 - 例如：
nums = [-1, -1, 2]，若不去重，i=2（值 2）时会重复记录[-1, -1, 2]。
- 当
左指针去重：
- 找到有效三元组后，若
nums[left]与nums[left-1]相同，left++跳过，避免重复使用相同元素。 - 例如：
nums = [-2, 0, 0, 2, 2]，避免因left指向不同位置的 0 或 2 导致重复。
- 找到有效三元组后，若
右指针去重：
- 类似左指针，若
nums[right]与nums[right+1]相同，right--跳过。
- 类似左指针，若
六、复杂度分析
| 复杂度类型 | 具体值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 排序耗时 O(n log n)，外层循环 O(n)，内层双指针循环 O(n)，整体由 O(n²) 主导 |
| 空间复杂度 | O(log n) 或 O(n) | 取决于排序算法的空间复杂度（如快速排序为 O(log n)，归并排序为 O(n)），结果存储不计入额外空间 |
七、举一反三
三数之和的“固定一个元素 + 双指针”思路可推广到：
- N数之和问题（如明天的四数之和）：固定 N-2 个元素，转化为两数之和。
- 带约束的组合问题：如寻找和为目标值的 k 个元素，且元素不重复。
下一题预告：LeetCode 18. 四数之和！这道题在三数之和基础上增加了一个固定元素，需要处理更多层的去重逻辑和边界条件，同时需注意目标值不是固定的 0 而是输入的 target，进一步考验对多指针和去重的掌握。
✨ 如果你觉得这篇解析有帮助，不妨：
🌟 点个赞，让更多人看到这份实用思路
⭐ 收个藏，下次遇到类似问题能快速复习
👀 加个关注，明天的三数之和解析更精彩
这是封面原图嘿嘿
