LeetCode15. 三数之和【双指针】

川长思鸟来 2023-01-22 07:54 11阅读 0赞

难度：中等  
题目描述：

> 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0  
> ？请你找出所有和为 0 且不重复的三元组。

注意：

> 答案中不可以包含重复的三元组。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            int n=nums.size();
            vector<vector<int>> ans;
            if(n<3){ 
                return ans;
            }
            vector<int> tmp;
            sort(nums.begin(),nums.end());
            for(int i=0;i<n-2;i++){ 
                if(i>0&&nums[i]==nums[i-1]){ 
                    continue;
                }
                int l=i+1,r=n-1;
                while(l<r){ 
                    if(nums[l]+nums[r]==-nums[i]){ 
                        tmp.clear();
                        tmp.push_back(nums[i]);
                        tmp.push_back(nums[l]);
                        tmp.push_back(nums[r]);
                        ans.push_back(tmp);
                        while(l<r&&nums[l]==nums[l+1]){ 
                            l++;
                        }
                        l++;
                        while(l<r&&nums[r]==nums[r-1]){ 
                            r--;
                        }
                        r--;
                    }else if(nums[l]+nums[r]<-nums[i]){ //说明应该向右
                        while(l<r&&nums[l]==nums[l+1]){ 
                            l++;
                        }
                        l++;
                    }else{ 
                        while(l<r&&nums[r]==nums[r-1]){ 
                            r--;
                        }
                        r--;
                    }
                }
            }
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221020/05be590a047e40d699b1374e16549b63.png