letecode 三数之和

一时失言乱红尘 2021-11-09 04:20 237阅读 0赞

letecode 15：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<time.h>
    using namespace std;
    class Solution{
    public:
        vector<vector<int>> threeSum(vector<int>& nums){    
        vector<vector<int>> res;
        if (nums.size()==0)
                 return {};
        sort(nums.begin(),nums.end());
        if( nums.front()>0 || nums.back()<0)
               return {};
        for(int i=0;i<nums.size();i++){
               if (nums[i]>0) break;
               if (i>0 && nums[i]==nums[i-1]) continue;
               int left=i+1,right=nums.size()-1;
               while(left<right){
                     if(nums[i]+nums[left]+nums[right]==0){
                          if(left==i+1||right==nums.size()-1){
                               res.push_back(vector<int> {nums[i],nums[left],nums[right]});
                               left++;
                               right--;
                          }
                          else if (nums[left]==nums[left-1]){
                               left++;
                          }
                          else if(nums[right]==nums[right+1]){
                               right--;
                          }
                          else{
                                res.push_back(vector<int> {nums[i],nums[left],nums[right]});
                                left++;
                                right--;}
                     }
                     else if(nums[i]+nums[left]+nums[right]<0)  left++;
                     else if(nums[i]+nums[left]+nums[right]>0)  right--;
                    
                      
                     }
               }
        
        return res;
        }         
        };
    
    int main(){
        Solution s;
        vector<vector<int>> res;
        vector<int> nums={3,0,-2,-1,1,2};
        res=s.threeSum(nums);
        for(int i=0;i<res.size();i++) {
            for( int j=0;j<res[i].size();j++){
                     cout<<res[i][j]<<'\t';  
            }
        }
        return 0;
    }

转载：[https://leetcode-cn.com/problems/3sum/solution/3sum-using-c-by-crunch/][https_leetcode-cn.com_problems_3sum_solution_3sum-using-c-by-crunch]

letcode 16:

#include<iostream>  
    #include<string> 
    #include<vector> 
    #include<algorithm>  
    using namespace std;
    class Solution{
    public:
        int threeSumClosest(vector<int>& nums, int target) {
             int ans0,ans1;
             sort(nums.begin(),nums.end());
    
             if (nums.empty()) return 0;  
            // if (nums.front()>target&&len>=3)   return  nums[0]+nums[1]+nums[2];
            // if (nums.back()<target&&len>=3)  return  nums[len-1]+nums[len-2]+nums[len-3];
             ans1=nums[0]+nums[1]+nums[2];
    
             for(int i=0;i<nums.size();i++){
                   //  if(nums[i]>target) break;
                     //if(i>0&&nums[i]==nums[i-1])  continue;
                     int left=i+1,right=nums.size()-1;
                    // cout<<"nums[i]:"<<nums[i]<<endl;;
                    // if (i==1) cout<<'\t'<<"ans1:"<<ans1<<"left:"<<left<<"right:"<<right<<endl;   
                     while(left<right){
                        int s=nums[left]+nums[i]+nums[right];
                        if (s==target) return target;
                        if  (abs(target-s)<abs(target-ans1)) {
                             ans1=s;
                        }
                        else if(s>target) 
                            right--; 
                        else if(s<target)
                             left++;
                      
                        
                       // if (i==1) cout<<'\t'<<"ans1:"<<ans1<<"left:"<<left<<"right:"<<right<<endl;  
                     } 
             }
             return ans1;
        }
    };
    
    int main(){    
       // vector<int> nums={0,2,1,-3};
        //vector<int> nums={1,2,4,8,16,32,64,128}
        vector<int> nums={6,-18,-20,-7,-15,9,18,10,1,-20,-17,-19,-3,-5,-19,10,6,-11,1,-17,-15,6,17,-18,-3,16,19,-20,-3,-17,-15,-3,12,1,-9,4,1,12,-2,14,4,-4,19,-20,6,0,-19,18,14,1,-15,-5,14,12,-4,0,-10,6,6,-6,20,-8,-6,5,0,3,10,7,-2,17,20,12,19,-13,-1,10,-1,14,0,7,-3,10,14,14,11,0,-4,-15,-8,3,2,-5,9,10,16,-4,-3,-9,-8,-14,10,6,2,-12,-7,-16,-6,10};
        //vector<int> nums={0,1,2};
        Solution s;
        int target=1;
        cout<<s.threeSumClosest(nums,-52);
        return 0;
    }

[https_leetcode-cn.com_problems_3sum_solution_3sum-using-c-by-crunch]: https://leetcode-cn.com/problems/3sum/solution/3sum-using-c-by-crunch/