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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

 

思路：

讨论里有说O(N²)的解法，好像是分为两个2 Sum来做。没仔细看。

下面贴个常规O(n³)解法，注意去重。 

vector
     
      
        > fourSum(vector
       
         &num, int target) {        vector
        
         
          > ans;        if(num.size() < 4) return ans;        int l1, l2, l3, l4;        sort(num.begin(), num.end());        for(l1 = 0; l1 < num.size() - 3; l1++)        {            if(l1 > 0 && num[l1] == num[l1 - 1]) continue; //注意去重复方法 含义是在另外三个数字固定的情况下 同一位置的数字不能重复            for(l4 = num.size() - 1; l4 >= l1 + 3; l4--)            {                if(l4 < num.size() - 1 && num[l4] == num[l4 + 1]) continue;                l2 = l1 + 1;                l3 = l4 - 1;                while(l2 < l3)                {                    if(num[l1]+num[l2]+num[l3]+num[l4] == target)                    {                        vector
          
            partans; partans.push_back(num[l1]); partans.push_back(num[l2]); partans.push_back(num[l3]); partans.push_back(num[l4]); ans.push_back(partans); l2++; while(num[l2] == num[l2 - 1]) { l2++; } l3--; while(num[l3] == num[l3 + 1]) { l3--; } } else if(num[l1]+num[l2]+num[l3]+num[l4] < target) { l2++; } else { l3--; } } } } return ans; }
          
         
        
       
      
     

 

大神看起来更统一的代码：

public class Solution {    public List
     
      
       > fourSum(int[] num, int target) {        List
       
        
         > results = new LinkedList
         
          
           >(); if (num == null || num.length < 4) return results; Arrays.sort(num); for (int s = 0; s < num.length - 3; s++) { if (s > 0 && num[s] == num[s - 1]) continue; for (int e = num.length - 1; e >= s + 3; e--) { if (e < num.length - 1 && num[e] == num[e + 1]) continue; int local = target - num[s] - num[e]; int j = s + 1; int k = e - 1; while (j < k) { if (j > s + 1 && num[j] == num[j - 1]) { j++; continue; } if (k < e - 1 && num[k] == num[k + 1]) { k--; continue; } if ((num[j] + num[k]) > local) k--; else if ((num[j] + num[k]) < local) j++; else results.add(new ArrayList
           
            (Arrays.asList( num[s], num[j++], num[k--], num[e]))); } } } return results; }}