18. 4Sum

 

QuestionEditorial Solution

 

 

• Total Accepted: 82006
• Total Submissions: 333565
• 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.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]

 

 to see which companies asked this question

Hide Tags

 

  

Show Similar Problems

 

 

题意以及题解转自：

【题意】

 

给定n个整数的数组S，是否在 数组S中有元素a，b，c，d，使得a + b + c + d = target？在数组中找出独一无二的四元素组，使得他们之和为target。

注意：

在四元素组（a，b，c，d）中，必须满足非递减排序。 （即a≤b≤c≤d）

该解决方案集中一定不能包含重复的四元素组。

【分析】

 

1. 对数组排序
2. 确定四元数中的前两个（a，b）
3. 遍历剩余数组确定两外两个（c，d），确定cd时思路跟确定后两个数据一样，二分查找左右逼近。
4. 在去重时采用set集合

 

1 class Solution { 2 public: 3     vector
      
       
        > fourSum(vector
        
         & nums, int target) { 4         vector
         
          
            > ans; 5         int sz = nums.size(); 6         int i,j,sum2,te; 7         int left,right; 8         set
           
            
              >s; 9 vector
             
               tmp;10 sort(nums.begin(),nums.end() );11 for(i = 0;i < sz - 3;i++) {12 if(i != 0 && nums[i] == nums[i - 1]) continue;13 for(j = i + 1;j < sz - 2;j++) {14 if(j != i + 1 && nums[j] == nums[j - 1]) continue;15 sum2 = nums[i] + nums[j];16 left = j + 1;right = sz - 1;17 while(left < right) {18 te = sum2 + nums[left] + nums[right];19 if(te == target) {20 tmp.clear();21 tmp.push_back(nums[i]);tmp.push_back(nums[j]);tmp.push_back(nums[left]);tmp.push_back(nums[right]);22 s.insert(tmp);23 left++;right--;24 }25 else if(te < target) {26 left++;27 }28 else{29 right--;30 }31 }32 }33 }34 set< vector
              
                >::iterator it;35 for(it = s.begin();it != s.end();it++) {36 ans.push_back(*it);37 }38 return ans;39 }40 };