PDF版 ePub版

# 4 Sum（4 个数的和）

(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

## 原文

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) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;

int len = nums.size();
for (int current = 0; current < len - 3;current++)
{
for(int second = current+1;second<len-2;second++)
{
int front = second + 1, back = len - 1;
while (front < back)
{
if (nums[current]+nums[second] + nums[front] + nums[back]  < target)
front++;
else if (nums[current] +nums[second]+ nums[front] + nums[back] > target)
back--;
else
{
vector<int> v(4);
v[0]=nums[current];
v[1]=nums[second];
v[2]=nums[front];
v[3]=nums[back];
result.push_back(v);
do {
front++;
} while (front < back&&nums[front - 1] == nums[front]);
do {
back--;
} while (front < back&&nums[back + 1] == nums[back]);
}
}
while(second < len-2&&nums[second+1]==nums[second])
second++;
}
while (current < len - 3 && nums[current + 1] == nums[current])
current++;
}
return result;
}
};