给你一个整数数组 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)实现,想当然了也是