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)

 

类似3Sum，先排序，这后两重for循环，然后对最后的一个数组设两个指针遍历。这里注意重复的问题，例如第一重如果和前面一个数相同则跳过，因为前面的查找肯定包含了本次的情况。

O(n^3)

1 class Solution { 2 private: 3     vector
     
      
        > ret; 4 public: 5     vector
       
        
          > fourSum(vector
         
           &num, int target) { 6         // Start typing your C/C++ solution below 7         // DO NOT write int main() function 8         sort(num.begin(), num.end()); 9         10         ret.clear();11         12         for(int i = 0; i < num.size(); i++)13         {14             if (i > 0 && num[i] == num[i-1])15                 continue;16                 17             for(int j = i + 1; j < num.size(); j++)18             {19                 if (j > i + 1 && num[j] == num[j-1])20                     continue;21                     22                 int k = j + 1;23                 int t = num.size() - 1;24                 25                 while(k < t)26                 {27                     if (k > j + 1 && num[k] == num[k-1])28                     {29                         k++;30                         continue;31                     }32                     33                     if (t < num.size() - 1 && num[t] == num[t+1])34                     {35                         t--;36                         continue;37                     }38                     39                     int sum = num[i] + num[j] + num[k] + num[t];40                     41                     if (sum == target)42                     {43                         vector
          
            a;44 a.push_back(num[i]);45 a.push_back(num[j]);46 a.push_back(num[k]);47 a.push_back(num[t]);48 ret.push_back(a);49 k++;50 }51 else if (sum < target)52 k++;53 else54 t--; 55 }56 }57 }58 59 return ret;60 }61 };