15. 3Sum(三数之和——）

た入场券 2022-12-02 11:00 117阅读 0赞

我还以为我写了blog3sum，结果没找都。那就再复习一遍  
给定阵列nums的Ñ整数，在那里元件a，b，c 在nums使得a + b + c = 0 在给出零总和的数组中找到所有唯一的三元组。(不能重复）  
注意：  
解决方案集不得包含重复的三个数。

例：  
给定数组nums = \[-1，0，1，2，-1，-4\]，  
一个解决方案集是：  
\[  
\[-1, 0, 1\],  
\[-1, -1, 2\]  
\]

思路：**如果用列举的方式来做，时间复杂度是O（N^3)，  
　　如果需要加速，我们通过先固定一个数字，然后从后面通过双指针的方式，大了right–,小了left++，当他们和为target之时，将他们压入ret，然后将相同的数字过滤掉（因为需要的是unique）** 需要在完成==target，压入时过滤left和right的相同的数，**同时最后还需要left，right同时往中间收缩否则出现endless Loop．**  
　　并且在第一个数结束自己的找target之后，也要过滤自己。**一共三个地方要进行去重，nums\[left\]，nums\[right\]，nums\[i\]**

code：  
**事件复杂度O（N^2), 空间复杂度O（1）**

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            if(nums.size()<3)
                return { };
            vector<vector<int>> res;
            //for unique.
            sort(nums.begin(),nums.end());
            for(int i=0;i<=nums.size()-3;i++){ 
                int target=-nums[i];
                int left=i+1,right=nums.size()-1;
                while(left<right){       
                    while(left<right&&  nums[left]+nums[right] > target){ 
                        right--;
                    }
                    while( left<right &&nums[right]+nums[left] < target){ 
                        left++;
                    }
                    if(left<right && nums[left]+nums[right]==target ){ 
                       res.push_back({ nums[i], nums[left], nums[right]});
                        while(left<right && nums[left]==nums[left+1])
                            left++;
                        while(left<right && nums[right]==nums[right-1])
                            right--;
                        right--,left++;     //take care :when finish first part,it goes to death path
                    }
                }
                //take care .if it needs unique vector,it should get rid of the same target
                while(i<nums.size()-3 && nums[i]==nums[i+1])
                    i++;
            }
            return res;
        }
    };