leetcode面试 150题之 三数之和 复刷日记

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