18. 4Sum

解题思路：

和15题3Sum如出一辙，在3Sum的解法外面再套一层即可。

实现代码：

// 18. 4Sum 
vector<vector<int>> fourSum(vector<int>& nums, int target) {
      vector<vector<int> > res;
  if (nums.size() < 4) return res;
  sort(nums.begin(), nums.end());
  int p, q, sum;
  for (int j = 0; j < nums.size() - 3; j++) {
    if (j > 0 && nums[j] == nums[j - 1])
      continue;
    int target3 = target - nums[j];  
    for (int i = j + 1; i < nums.size() - 2; i++) {
      if (i > j + 1 && nums[i] == nums[i - 1]) 
        continue;
      p = i + 1;
      q = nums.size() - 1;
      while (p < q) {
        sum = nums[i] + nums[p] + nums[q];
        if (sum == target3) {
          res.push_back({nums[j], nums[i], nums[p], nums[q]});
          while (nums[p] == nums[p + 1] && p < q)
            p++;
          p++;
          while (nums[q] == nums[q - 1] && p < q)
            q--;
          q--;
        } else if (sum > target3) {
          while (nums[q] == nums[q - 1] && p < q)
            q--;
          q--;
        } else {
          while (nums[p] == nums[p + 1] && p < q)
            p++;
          p++;
        }
      }
    }
  }
  return res;
}

问题描述：

Given an arraynumsofn_integers and an integertarget, are there elements_a,b,c, andd_innumssuch that_a+b+c+d=target? Find all unique quadruplets in the array which gives the sum oftarget.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [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]
]