Question：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<vector<int>> fourSum(vector<int>& nums, int target) {}
}

1 题目思路分析##

本题与3Sum的基本思路相同，都是先排序，然后先取好前两个数，最后两个数来夹逼。

1.1 基本思路( O(n^3) )###

按照基本思路，有两个版本，一个自己写的，一个是书里的，自己写的结果一个测试用例超时（64ms）， 书里的（44ms）过了，郁闷。

1.1.1 自己写的

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort( nums.begin(), nums.end() );
        int size= nums.size();
        auto last=nums.end();
        auto start=nums.begin();
        vector<vector<int>>result;
        
        if(size<4) return result;
        
        for(auto h=start; h<(last-3); h++)
        {
            if( h!=start && *h == *(h-1) ) continue;
            
            for (auto i=h+1; i<(last-2); i++)
            {
                if ( i!= (h+1) && *i==*(i-1) ) continue;
                    
                auto j=i+1;
                auto k=last-1;
                
                while (j<k)
                {
                    if (*h + *i + *j + *k < target)
                    {
                        j++;
                        while (*j == *(j-1) && j<k ) j++;
                    }
                    
                    else if(*h + *i + *j + *k > target)
                    {
                        k--;
                        while (*k == *(k+1) && j<k) k--;
                    }
                    
                    else
                    {
                        result.push_back({*h, *i, *j, *k});
                        j++;
                        k--;
                        while (*j==*(j-1) && *k==*(k+1) && j<k) j++;
                    }
                }
            }
            
        }
        
        return result;
    }
};

1.1.2 书上的

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& num, int target)
    {
        vector<vector<int>> result;
        if (num.size() < 4) return result;
        sort(num.begin(), num.end());
        auto last = num.end();
        for (auto a = num.begin(); a < prev(last, 3); ++a)
        {
            for (auto b = next(a); b < prev(last, 2); ++b)
            {
                auto c = next(b);
                auto d = prev(last);
                while (c < d)
                {
                    if (*a + *b + *c + *d < target) c++;
                    else if (*a + *b + *c + *d > target) d--;
                    else
                    {
                        result.push_back({ *a, *b, *c, *d });
                        ++c;
                        --d;
                    }
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};

1.2 优化

书上讲了几个优化的方法

1.2.1 利用map来缓存前两个的和####

unordered_map< int, vector< pair< int, int> > > cache;

class Solution {
public:
   vector<vector<int> > fourSum(vector<int> &num, int target)
   {
       vector<vector<int>> result;
       if (num.size() < 4) return result;
       sort(num.begin(), num.end());
       unordered_map<int, vector<pair<int, int> > > cache;
       
       for (size_t a = 0; a < num.size(); ++a)
       {
           for (size_t b = a + 1; b < num.size(); ++b)
           {
               cache[num[a] + num[b]].push_back(pair<int, int>(a, b));
           }
       }
       for (int c = 0; c < num.size(); ++c)
       {
           for (size_t d = c + 1; d < num.size(); ++d)
           {
               const int key = target - num[c] - num[d];
               if (cache.find(key) == cache.end()) continue;
               const auto& vec = cache[key];
               for (size_t k = 0; k < vec.size(); ++k)
               {
                   if (c <= vec[k].second) continue;
                   result.push_back( { num[vec[k].first], num[vec[k].second], num[c], num[d] });
               }
           }
       }
       sort(result.begin(), result.end());
       result.erase(unique(result.begin(), result.end()), result.end());
       return result;
   }
};

1.2.1 利用multi_map来缓存前两个的和####

用一个 hashmap 先缓存两个数的和,时间复杂度 O(n^2),空间复杂度 O(n^2)
// @author 龚陆安 (http://weibo.com/luangong)

class Solution {
public:
      vector<vector<int>> fourSum(vector<int>& num, int target) 
      {
          vector<vector<int>> result;
          if (num.size() < 4) return result;
          sort(num.begin(), num.end());
          unordered_multimap<int, pair<int, int>> cache;
          for (int i = 0; i + 1 < num.size(); ++i)
              for (int j = i + 1; j < num.size(); ++j)
                  cache.insert(make_pair(num[i] + num[j], make_pair(i, j)));//!!!!!!!!!!!!!!!!!!!
          for (auto i = cache.begin(); i != cache.end(); ++i) 
          {
              int x = target - i->first;
              auto range = cache.equal_range(x);
              for (auto j = range.first; j != range.second; ++j) 
              {
                  auto a = i->second.first;
                  auto b = i->second.second;
                  auto c = j->second.first;
                  auto d = j->second.second;
                  if (a != c && a != d && b != c && b != d) 
                  {
                      vector<int> vec = { num[a], num[b], num[c], num[d] };
                      sort(vec.begin(), vec.end());
                      result.push_back(vec);
                  }
              }
          }
          sort(result.begin(), result.end());
          result.erase(unique(result.begin(), result.end()), result.end());
          return result;
     }
 };