【LeetCode】018 4Sum

题目：

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]
]

题解：

　　这个题与3Sum类似，求4Sum就在原基础上再加上一层循环就可以了。这里只给出此种解法思路的其中一个解法。

Solution 1 (36ms)

 1 class Solution {
 2 public:
 3     vector<vector<int>> fourSum(vector<int>& nums, int target) {
 4          set<vector<int>> sv;
 5          sort(nums.begin(), nums.end());
 6          int n = nums.size();
 7 
 8          for(int i=0; i<n-3; i++) {
 9              for(int j=i+1; j<n-2; j++) {
10                  int k = j+1, l = n-1;
11                  int a = nums[i], b = nums[j];
12                  while(k<l) {
13                      int c = nums[k], d = nums[l];
14                      if(a+b+c+d == target) {
15                          sv.insert({a,b,c,d});
16                          k++;
17                          l--;
18                      }
19                      else if(a+b+c+d < target) k++;
20                      else l--;
21                  }
22              }    
23          }
24          return vector<vector<int>> (sv.begin(),sv.end());            
25     }
26 };

　　还有一种解法，也是利用了3Sum，不过不是再加一层循环，而是直接调用3Sum函数：取nums[i]，然后对后续剩余数组元素求3Sum，tar为target - nums[i]；

Solution 2 (32ms)

 1 class Solution {
 2 public:
 3     vector<vector<int> > threeSum(vector<int> &nums, int target) {
 4         set<vector<int>> sv;
 5         sort(nums.begin(), nums.end());
 6         int n = nums.size();
 7 
 8         for(int i=0; i<n-2; i++) {
 9             int a = nums[i];
10             int j = i+1, k = n-1;
11             while(j<k) {
12                 int b = nums[j], c = nums[k];
13                 if(a+b+c == target) {
14                     sv.insert({a,b,c});
15                     j++;
16                     k--;
17                 }
18                 else if(a+b+c > target) k--;
19                 else j++;
20             }
21         }
22         return vector<vector<int>> (sv.begin(),sv.end());
23     }
24      vector<vector<int>> fourSum(vector<int>& nums, int target) {
25          vector<vector<int>> vv;
26          sort(nums.begin(), nums.end());
27          int n = nums.size();
28 
29          for(int i=0; i<n-3; i++) {
30              if(i>0 && nums[i] == nums[i-1]) continue;
31              //截取剩余数组
32              vector<int> v(nums.begin()+i+1,nums.end());
33              vector<vector<int>> tmp = threeSum(v, target - nums[i]);
34              for(int j=0; j<tmp.size(); j++) {
35                  tmp[j].insert(tmp[j].begin(), nums[i]);
36                  vv.push_back(tmp[j]);
37              }
38          }
39          return vv;            
40     }
41 };

　　还有一种更为优化的解法，思路是一致的，只是加了一个小技巧：在两个外循环中先判断四个值的和与target的大小，即

　　if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
　　if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;

　　通过这两条语句减少了搜索时间，不必进入内循环判断；对于j同理。

Solution 3 (12ms)

 1 class Solution {
 2 public:
 3     vector<vector<int>> fourSum(vector<int>& nums, int target) {
 4          set<vector<int>> sv;
 5          sort(nums.begin(), nums.end());
 6          int n = nums.size();
 7          if(n<4)  return vector<vector<int>> (sv.begin(),sv.end());
 8          for(int i=0; i<n-3; i++) {
 9              if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
10              if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
11              if(i>0&&nums[i]==nums[i-1]) continue;
12              for(int j=i+1; j<n-2; j++) {
13                  if(j>i+1&&nums[j]==nums[j-1]) continue;
14                 if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
15                 if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
16                  int k = j+1, l = n-1;
17                  int a = nums[i], b = nums[j];
18                  while(k<l) {
19                      int c = nums[k], d = nums[l];
20                      if(a+b+c+d == target) {
21                          sv.insert({a,b,c,d});
22                          k++;
23                          l--;
24                      }
25                      else if(a+b+c+d < target) k++;
26                      else l--;
27                  }
28              }    
29          }
30          return vector<vector<int>> (sv.begin(),sv.end());            
31     }
32 };

Solution 4

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n - 3; ++i){
            for(int j = i + 1; j < n - 2; ++j){
                int begin = j + 1, end = n - 1;
                while(begin < end){
                    int sum = nums[i] + nums[j] + nums[begin] + nums[end];
                    if(sum == target)
                        res.push_back({nums[i], nums[j], nums[begin++], nums[end--]});
                    else if (sum < target)
                        ++begin;
                    else
                        --end;
                }
            }
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        return res;
    }
};

去重的另一种方法，使用了algorithm

Solution 5

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        unordered_multimap<int, pair<int, int>> map;
        for(int i = 0; i < n - 1; ++i){
            for(int j = i + 1; j < n; ++j){
                map.insert(make_pair(nums[i] + nums[j], make_pair(i, j)));
            }
        }
        for(auto i = map.begin(); i != map.end(); ++i){
            int val = target - i->first;
            auto range = map.equal_range(val);
            for(auto j = range.first; j != range.second; ++j){
                auto a = i->second.first, b = i->second.second;
                auto c = j->second.first, d = j->second.second;
                if(a != c && a != d && b != c && b != d){
                    vector<int> tmp = {nums[a], nums[b], nums[c], nums[d]};
                    sort(tmp.begin(), tmp.end());
                    res.push_back(tmp);
                }
            }
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        return res;
    }
};

先缓存两个数的和，注意要使用multimap（from 九章算法）