先来一个暴力解：

class Solution {public:    vector
     
      
        > fourSum(vector
       
         &num, int target) {        vector
        
         
           > res;        vector
          
            r; r.resize(4); sort(num.begin(), num.end()); int len = num.size(); for (int i=0; i
           
            = 0 && psum > target) break; if (j!=i+1 && num[j] == num[j-1]) continue; // skip dup r[0] = num[i], r[1] = num[j]; int ptarget = target - psum; int p = j+1; int q = len - 1; while (p < q) { if (num[p] >= 0 && num[p] > ptarget) break; if (num[q] < 0 && num[q] < ptarget) break; if (p != j+1 && num[p] == num[p-1]) { // skip dup p++; continue; } if (q != len-1 && num[q] == num[q+1]) { // skip dup q--; continue; } int s = num[p] + num[q]; if (s < ptarget) { p++; } else if (s > ptarget) { q--; } else { r[2] = num[p]; r[3] = num[q]; res.push_back(r); p++, q--; } } } } return res; }};
           
          
         
        
       
      
     

有些快速跳出的语句加了反而更慢。

第二轮：

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)

class Solution {public:    vector
     
      
        > fourSum(vector
       
         &num, int target) {        sort(num.begin(), num.end());                vector
        
         
           > res;        int len = num.size();        if (len < 4) {            res;        }                for (int i=0; i
          

({num[i], num[j], num[p], num[q]})); } p++; } else if (t > rest) { q--; } else { p++; } } } } return res; }};