# 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int target = 0;
int nums[] = {1, 0, -1, 0, -2, 2};
int length1 = sizeof(nums) / sizeof(nums[0]);
vector nums1(nums, nums + length1);
vector> res;
res = sol.fourSum(nums1, target);
for (auto i : res)
{
for (auto j : i)
cout << j << ' ';
cout << endl;
}
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
vector> fourSum(vector &nums, int target)
{
vector> res;
vector temp;
sort(nums.begin(), nums.end());
for (int base_begin = 0; base_begin < nums.size(); base_begin++)
{
if (base_begin > 0 && nums.at(base_begin) == nums.at(base_begin - 1))
continue;
for (int base_end = nums.size() - 1; base_end > base_begin + 2; base_end--)
{
int left = base_begin + 1;
int right = base_end - 1;
while (left < right)
{
int tt = nums.at(base_begin) + nums.at(base_end) + nums.at(left) + nums.at(right);
if (tt > target)
right--;
else
{
temp.clear();
temp.push_back(nums.at(base_begin));
temp.push_back(nums.at(left));
temp.push_back(nums.at(right));
temp.push_back(nums.at(base_end));
res.push_back(temp);
++left;
--right;
}
}
}
}
return res;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector> fourSum(vector &nums, int target)
{
vector> res;
sort(nums.begin(), nums.end());
if (nums.size() < 4)
return res;
for (int a = 0; a < nums.size() - 3; ++a)
{
if (a > 0 && nums[a] == nums[a - 1])
{
continue;
}
for (int b = a + 1; b < nums.size() - 2; ++b)
{
if (b > a + 1 && nums[b] == nums[b - 1])
{
continue;
}
int c = b + 1, d = nums.size() - 1;
while (c < d)
{
int sum = nums[a] + nums[b] + nums[c] + nums[d];
if (sum < target)
{
c++;
}
else if (sum > target)
{
d--;
}
else
{
res.push_back({nums[a], nums[b], nums[c], nums[d]});
while (c < d && nums[c] == nums[c + 1])
{
c++;
}
while (c < d && nums[d - 1] == nums[d])
{
d--;
}
c++;
d--;
}
}
}
}
return res;
}
};
```
### B
```cpp
class Solution
{
public:
vector> fourSum(vector &nums, int target)
{
if (nums.size() < 4)
return {};
sort(nums.begin(), nums.end());
vector> res;
set> a;
for (int i = 0; i < nums.size() - 3; i++)
{
if (nums[i] > target && target > 0)
break;
for (int j = i + 1; j < nums.size() - 2; j++)
{
int l = j + 1;
int r = nums.size() - 1;
while (l < r)
{
if (nums[i] + nums[j] + nums[l] + nums[r] < target)
l++;
else if (nums[i] + nums[j] + nums[l] + nums[r] > target)
r--;
else
{
vector temp{nums[i], nums[j], nums[l], nums[r]};
a.insert(temp);
l++;
r--;
}
}
}
}
for (auto c : a)
{
res.push_back(c);
}
return res;
}
};
```
### C
```cpp
class Solution
{
public:
vector> fourSum(vector &nums, int target)
{
if (nums.size() < 4)
return {};
sort(nums.begin(), nums.end());
set> a;
vector> res;
for (int i = 0; i < nums.size() - 3; i++)
{
if (nums[i] > target && target > 0)
break;
for (int j = i + 1; j < nums.size() - 2; j++)
{
for (int l = j + 1; l < nums.size() - 1; l++)
{
for (int r = l + 1; r < nums.size(); r++)
{
if (nums[i] + nums[j] + nums[l] + nums[r] == target)
a.insert(vector{nums[i], nums[j], nums[l], nums[r]});
}
}
}
}
for (auto c : a)
{
res.push_back(c);
}
return res;
}
};
```