# 四数之和

<p>给定一个包含 <em>n</em> 个整数的数组 <code>nums</code> 和一个目标值 <code>target</code>，判断 <code>nums</code> 中是否存在四个元素 <em>a，</em><em>b，c</em> 和 <em>d</em> ，使得 <em>a</em> + <em>b</em> + <em>c</em> + <em>d</em> 的值与 <code>target</code> 相等？找出所有满足条件且不重复的四元组。</p><p><strong>注意：</strong>答案中不可以包含重复的四元组。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums = [1,0,-1,0,-2,2], target = 0<strong><br />输出：</strong>[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums = [], target = 0<strong><br />输出：</strong>[]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= nums.length <= 200</code></li>	<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>	<li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
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<int> nums1(nums, nums + length1);

    vector<vector<int>> 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<vector<int>> fourSum(vector<int> &nums, int target)
    {
        vector<vector<int>> res;
        vector<int> 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<vector<int>> fourSum(vector<int> &nums, int target)
    {
        vector<vector<int>> 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<vector<int>> fourSum(vector<int> &nums, int target)
    {
        if (nums.size() < 4)
            return {};
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        set<vector<int>> 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<int> 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<vector<int>> fourSum(vector<int> &nums, int target)
    {
        if (nums.size() < 4)
            return {};
        sort(nums.begin(), nums.end());
        set<vector<int>> a;
        vector<vector<int>> 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<int>{nums[i], nums[j], nums[l], nums[r]});
                    }
                }
            }
        }
        for (auto c : a)
        {
            res.push_back(c);
        }
        return res;
    }
};
```
