18. 4Sum

• Total Accepted: 80288
• Total Submissions: 328279
• Difficulty: Medium

 

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

 

 

思路：基本思想和类似，只是数的个数变为4。

 

代码：

1 class Solution { 2 public: 3     vector
     
      
        > fourSum(vector
       
        & nums, int target) { 4         vector
        
         
           > res; 5         int n=nums.size(); 6         if(n<4) return res; 7         sort(nums.begin(),nums.end()); 8         int i,j,k,l,ans; 9         for(i=0;i
          
           target) break;11 if(nums[i]+nums[n-1]+nums[n-2]+nums[n-3]
           
            0&&nums[i]==nums[i-1]) i++;13 for(j=i+1;j
            
             target) break;15 if(nums[i]+nums[n-1]+nums[n-2]+nums[j]
             
              i+1&&nums[j]==nums[j-1]) j++;17 k=j+1;18 l=n-1;19 while(k
              
               =target) l--;27 if(ans<=target) k++;28 }29 }30 }31 return res;32 }33 };