力扣-15题三数之和（C++）- 有价值+双指针

た入场券 2022-09-09 00:29 215阅读 0赞

题目链接：[https://leetcode-cn.com/problems/3sum/][https_leetcode-cn.com_problems_3sum]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
思路示例：  
![在这里插入图片描述][97b6c7650a0e47f68b22e61b84f5b9f9.gif]

class Solution {
        
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
        
            vector<vector<int>> result;
    
            sort(nums.begin(),nums.end());//升序排序
            for(int i=0;i<nums.size();i++){
        
                if(nums[i]>0) return result;//如果第一个元素>0，那么组合不可能凑成
                if(i>0&&nums[i]==nums[i-1]) continue;//去重
    
                int left=i+1;
                int right=nums.size()-1;
                while(right>left){
        
                    if(nums[i]+nums[left]+nums[right]>0) right--;
                    else if(nums[i]+nums[left]+nums[right]<0) left++;
                    else{
        
                        result.push_back(vector<int>{
        nums[i],nums[left],nums[right]});
                        //去重逻辑应该放在找到一个三元组之后
                        while(right>left&&nums[right]==nums[right-1]) right--;
                        while(right>left&&nums[left]==nums[left+1]) left++;
    
                        right--;//找到答案时，双指针同时收缩
                        left++;
                    }
                }
    
            }
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_3sum]: https://leetcode-cn.com/problems/3sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ec462e6f0bec4a8bb3a4ea5502d74694.png
[97b6c7650a0e47f68b22e61b84f5b9f9.gif]: /images/20220829/1dab4311b5e44086b19cf6970a6967cf.png