【LeetCode】15.三数之和

目录 题目题目要求算法解法算法一： 排序 + 暴力枚举 + set去重 （O( n 3 n^{3} n3)）算法二： 排序 + 双指针 代码

题目

题目链接：LeetCode-15题

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。

题目要求 满足 i != j、i != k 且 j != k （下标不同）nums[i] + nums[j] + nums[k] == 0不重复的三元组 算法解法 算法一： 排序 + 暴力枚举 + set去重 （O( n 3 n^{3} n3)）

排序再枚举，可以将重复的三元组变成相同的三元组，再去重即可。

简单解法，不讲解。

算法二： 排序 + 双指针

一旦排序应该思考能否使用双指针或者二分。

排序固定一个数a在该数后面的区间内，利用双指针算法一直寻找两个数的和等于-a即可双指针算法：因为排序了，所以如果两个数相加如果大于目标值，说明中间的数字已经不可能等于目标值了，只有减小最大值（right–），才有机会得到目标值。反之，如果两个数相加小于目标值，直接left++； 细节问题： 去重 因为排序，我们会获得相同的结果，所以我们固定的数字如果与前一个相同，需要跳过。（跳过重复元素）双指针算法之间，left和right指针也需要跳过重复元素，原因是因为两个数字相加已经得到了-a，那么这两个数字必须一起存在才能得到对应的-a。也就是要么重复这两个数字，要么不能得到-a。 代码 class Solution { public: vector<vector<int>> ret; vector<vector<int>> threeSum(vector<int>& nums) { //排序 sort(nums.begin(),nums.end()); int n = nums.size(); for(int i =0;i<n;) //固定数a { //利用双指针解决问题 int left = i+1; int right = n-1; int 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--; //去重并且防止越界 while(nums[left] == nums[left-1] && left < right)left++; while(nums[right] == nums[right+1] && right > left)right--; } } //去重固定元素 i++; while(i<n && nums[i] == nums[i-1]) i++; } return ret; } };