leecode第十五题(三数之和)

leecode第十五题(三数之和)

 

class Solution {
public:
    void quick_order(vector<int>& num, int star, int en)//快排
    {
        int start = star;
        int end = en;
        if (start >= end)
            return;

        int index = num[start];//就第一个设为阈值
        while (start < end)
        {
            while (start < end && index <= num[end])//先看右边,把第一个小于index数找出
                end--;

            int temp1 = num[start];//交换
            num[start] = num[end];
            num[end] = temp1;

            while (start < end && index >= num[start])//再看右边,把第一个大于index的数找出
                start++;

            int temp2 = num[start];//交换
            num[start] = num[end];
            num[end] = temp2;
        }

        quick_order(num, star, start-1);//分左右子集迭代
        quick_order(num, start + 1, en);
        return;
    }
    
    vector<vector<int>> threeSum(vector<int>& nums) {        
        int len=nums.size();
        vector<vector<int>> res;
        
        if(len==0)//输入判断
            return res;
        
        int start=0,end=len-1;
        quick_order(nums,start,end);//快排
        
        vector<vector<int>> v2;
        for (int c = nums.size()-1; c >= 2; ){
            for (int a = 0, b = c-1; a < b; ){
                int tmp_sum = nums[a]+nums[b];
                if (tmp_sum < -nums[c]){
                    ++a;
                } else if (tmp_sum > -nums[c]){
                    --b;
                } else {
                    vector<int> v = {nums[a], nums[b], nums[c]};
                    v2.push_back(v);
                    do{//去重复 a b
                        ++a;
                    } while (a < b && nums[a-1] == nums[a]);
                    do{
                        --b;
                    } while (a < b && nums[b+1] == nums[b]);
                }
            }
            do{//去重复 c
                --c;
            } while (c >= 2 && nums[c+1] == nums[c]);
        }
        return v2;

     /*for(int fir=1;fir<len-1;fir++)
        {
            int sec=fir-1,thr=fir+1;
            while(sec>=0 && thr<=len-1)
            {
                int sum=nums[fir]+nums[sec]+nums[thr];
                if (sum==0)
                {
                    vector<int> node={nums[sec],nums[fir],nums[thr]};
                    bool flag=true;
                    for(int i=0;i<res.size();i++)
                    {
                        if(node==res[i])
                            flag=!flag;
                    }
                    if(flag)
                        res.push_back(node);
                    sec = sec - 1;
                }
                else if (sum>0)
                    sec=sec-1;
                else if (sum<0)
                    thr=thr+1;
            } 
        }
        
        return res;*/
    }

};

 

分析:

不写代码永远不知道自己有多菜,一个快排写的我哭了,然后说主要思想:

未注释的是别人的代码,排序后,令【a,。。。。,b,c】这种形式,让c从右往左遍历,a初始化为0,从左向右移动,b初始化c-1,从右往左移动。在c遍历中,计算a+b,若a+b<-c,说明a太小了,a++,若a+b>-c,说明b大了,b--。最让我值得学习的是去重复,其实不难,就是a,b,c在各自道路上有重复就前进。

注释的是我自己的想法,排序后,令【。。。a,b,c,。。。】这种形式,b从左向右遍历,a初始化b-1,从b往左移动,c初始化b+1,从b往右移动。在b遍历中,计算a+c,若a+b+c>0,a--,若a+b+c<0,b++。这里已经实现了除去重复所有功能,且时间复杂度和上面一样,但是就在去重复这里我懵了,我先按查找已被选择的三数,但是碰到一个变态长的数组,时间复杂度蹭蹭的上涨,然后我就分析重复情况,有两个例子【-1,0,0,1】和【-2,-1,-1,0,1,2】,一个是【【-1,0,1】】,一个是【【-1,-1,2】,【-1,0,1】】,这里面如果你让b跳过重复的,那就错过后面案例的【-1,-1,2】,如果不跳过,前面案例就会重复,搞的我又一点点分析,但是真的好难写,难写在于解决一个情况,但是又有新的情况,二者特矛盾,有一没二那种,后来代码越写越长,还丑,我就只能捂着脸学习别人的思想了。

下次再碰到想到中间指针时候,想想指针从后向前或从前向后的情况。

上一篇:leecode第十六题(最接近的三数之和)


下一篇:leecode第四题(寻找两个有序数组的中位数)