15. 三数之和
3 min
题目
思路
核心思想是排序后使用双指针技巧。首先固定一个数，然后在剩余部分用双指针寻找两数之和等于该数的相反数。
正确性基于数组有序性：当三数之和大于0时，右指针左移可减小总和；小于0时左指针右移可增加总和。跳过重复值确保不产生重复三元组，因为相同值的组合已被前置指针处理过。
- Step 1: 对数组排序，便于双指针操作和去重
- Step 2: 遍历数组，固定第一个数 nums[i]，跳过重复值
- Step 3: 初始化指针 j=i+1 和 k=n-1
- Step 4: 当 j<k 时循环：若和大于0则 k—；若等于0则记录三元组并 j++
- Step 5: 内层循环中跳过重复的 nums[j] 值
复杂度
- 时间复杂度: ，其中 是数组长度。排序 可忽略，双指针两层循环占主导。
- 空间复杂度: ，排序算法的栈空间开销（快速排序递归深度）。
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
for(int i =0;i < nums.size();i++){
if(i > 0 and nums[i] == nums[i-1])
continue;
int k = nums.size()-1;
for(int j = i+1;j < nums.size();j++){
if(j > i+1 and nums[j] == nums[j-1])
continue;
while(j < k and nums[i] + nums[j] + nums[k] > 0){
k--;
}
if(j == k)
break;
if(nums[i] + nums[j] + nums[k] == 0){
ans.push_back({nums[i],nums[j],nums[k]});
}
}
}
return ans;
}
};