三数之和
题目描述
给你一个整数数组 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。
题目大意
给定一个数组，找出三个数使其和为目标值 0，返回所有符合条件的三元组。 本题和两数之和存在区别：两数之和返回元素下标，本题返回元素本身；同时本题要求最终结果不能出现重复三元组。
解题思路
O
(
N
3
)
O(N^3)
O(N3)，效率极低。
- 先对数组排序，方便后续去重与双指针查找；
- 固定第一个数 nums[i]，将问题转化为：在 i 之后的区间内，寻找两数之和等于 0 – nums[i]；
- 使用左右双指针遍历剩余区间，匹配目标两数和；
- 增加去重逻辑，保证最终三元组不重复；
- 整体时间复杂度
O
(
N
2
)
O(N^2)
O(N2)。
关键去重逻辑说明
if(i > 0 && nums[i] == nums[i-1]) continue; 跳过重复的第一个数。保证对于连续相同数字，仅以第一个元素作为固定值进行查找，避免产生重复三元组。
if(l > i + 1 && nums[l] == nums[l-1]){l++;continue;} 跳过双指针区间内重复的左指针元素，防止同一组合重复收录。
右指针无需单独写重复判断：当两数和大于目标值时右指针持续左移，会自动跳过重复值。
代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int target = 0;
int n = nums.size();
sort(nums.begin(),nums.end());
vector<vector<int>> ans;
for(int i = 0; i < n; i++){
// 对固定位 i 去重
if(i > 0 && nums[i] == nums[i–1]) continue;
int te = target – nums[i];
int l = i + 1, r = n – 1;
while(l < r){
// 对左指针去重
if(l > i + 1 && nums[l] == nums[l–1]){
l++;
continue;
}
// 和偏大，右指针左移
while(l < r && nums[l] + nums[r] > te) r—;
if(l == r) break;
// 找到符合条件的三元组
if(nums[l] + nums[r] == te){
ans.push_back({nums[i],nums[l],nums[r]});
}
l++;
}
}
return ans;
}
};
每日心灵鸡汤
深耕算法细节，吃透逻辑原理，方能举一反三、从容解题。
