给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
题目重点 不重复的三数和为0
这里如果是暴力做法也就是三层for循环去暴力遍历
我先想到的是双指针固定两个数然后二分找第三个数(有点想当然)
这里代码只能处理一半的数据 当遇到 -4 -2 -2 0 2 2 4时就漏情况了,而且处理起来非常麻烦
我的逻辑是排序后左右指针分别确定一个数,当左右指针之间没有元素或者相乘同号则结束查找,否则去寻找三个数
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
int l=0,r=n-1;
vector<vector<int>> tar;
while(l<r-1&&nums[l]*nums[r]<=0)
{
int value=nums[l]+nums[r];
if((l>=1&&nums[l]==nums[l-1])||(value+nums[r]<0)){l++;continue;};
if((r<n-1&&nums[r]==nums[r+1])||(value+nums[l]>0)){r--;continue;};
int left=l+1,right=r,mid=0;
while(left<right)
{
mid=(left+right)/2;
if(nums[mid]+value==0)
{
tar.push_back({nums[l],nums[mid],nums[r]});
break;
}
else if(nums[mid]+value>0) right=mid;
else left=mid+1;
}
if(value>0) r--;
else l++;
}
return tar;
}
};
然后我尝试只固定一个值,因为上面的 -4 -2 -2 0 2 2 4 中就是因为我锁定l,r导致无论是l++,还是r--都会丢掉一个解
这里我们选择了一个值后 再去通过双指针找与该值到和为0的二元组,这里的去重就简单了,已经固定了一个值,这里的二元组只要有一个和之前的相等则指针相应的++或者--直到找不到二元组和固定值为相反数为止
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> tar;
for(int i=0;i<nums.size()-2;i++)
{
int l=i+1,r=nums.size()-1;
if(i>=1&&nums[i]==nums[i-1]) continue;
while(l<r)
{
int value=nums[l]+nums[r]+nums[i];
if(value>0) r--;
else if(value<0) l++;
else
{
tar.push_back({nums[i],nums[l],nums[r]});
while (l < r && nums[l] == nums[l + 1]) l++; //去重
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
return tar;
}
};
这里的时间复复杂度为O(n*n) 我以为我的方法能O(nlogn)实现,想当然了也是