# 三数之和

<p>给你一个包含 <code>n</code> 个整数的数组 <code>nums</code>，判断 <code>nums</code> 中是否存在三个元素 <em>a，b，c ，</em>使得 <em>a + b + c = </em>0 ？请你找出所有和为 <code>0</code> 且不重复的三元组。</p><p><strong>注意：</strong>答案中不可以包含重复的三元组。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums = [-1,0,1,2,-1,-4]<strong><br />输出：</strong>[[-1,-1,2],[-1,0,1]]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums = []<strong><br />输出：</strong>[]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>nums = [0]<strong><br />输出：</strong>[]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= nums.length <= 3000</code></li>	<li><code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code></li></ul>
<p>以下错误的选项是？</p>

## aop
### before
```cpp
#include <vector>
#include <iostream>
#include <set>

using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    int arr[] = {-1,0,1,2,-1,-4};
    int length1 = sizeof(arr) / sizeof(arr[0]);
    vector<int> nums(arr, arr + length1);
    vector<vector<int> > res;
    res = sol.threeSum(nums);

    for (auto i : res)
    {
        for (auto j : i)
            cout << j << ' ';
        cout << endl;
    }
    return 0;
}

```

## 答案
```cpp
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<vector<int>> ans;
        if (nums.empty())
            return {};
        for (int i = 0; i < len; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int newtar = -nums[i];
            int low = i + 1;
            int high = len - 1;
            while (low < high)
            {
                if (nums[low] + nums[high] == newtar)
                {
                    ans.push_back({nums[i], nums[low], nums[high]});
                    while (low < high && nums[low] == nums[low + 1])
                        ++low;
                    while (low < high && nums[high] == nums[high - 1])
                        --high;
                }
                else
                    high--;
            }
        }
        return ans;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        if (nums.size() < 3 || nums.front() > 0 || nums.back() < 0)
            return {};
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i++)
        {
            int fix = nums[i];
            if (fix > 0)
                break;
            if (i > 0 && fix == nums[i - 1])
                continue;
            int l = i + 1;
            int r = nums.size() - 1;
            while (l < r)
            {
                if (nums[l] + nums[r] == -fix)
                {
                    if (l == i + 1 || r == nums.size() - 1)
                    {
                        res.push_back(vector<int>{nums[i], nums[l], nums[r]});
                        l++;
                        r--;
                    }
                    else if (nums[l] == nums[l - 1])
                        l++;
                    else if (nums[r] == nums[r + 1])
                        r--;
                    else
                    {
                        res.push_back(vector<int>{nums[i], nums[l], nums[r]});
                        l++;
                        r--;
                    }
                }
                else if (nums[l] + nums[r] < -fix)
                    l++;
                else
                    r--;
            }
        }
        return res;
    }
};
```

### B
```cpp
class Solution
{
public:
    static bool cmp(const int &a, const int &b)
    {
        return a < b;
    }
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end(), cmp);
        vector<int>::iterator it;
        vector<vector<int>> res;
        set<vector<int>> a;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] > 0)
                break;
            for (int j = i + 1; j < nums.size(); j++)
            {
                it = find(nums.begin() + j + 1, nums.end(), 0 - nums[i] - nums[j]);
                if (it != nums.end())
                {
                    vector<int> temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[j]);
                    temp.push_back(*it);
                    a.insert(temp);
                }
            }
        }
        for (auto k : a)
        {
            res.push_back(k);
        }
        return res;
    }
};
```

### C
```cpp
class Solution
{
public:
    vector<vector<int> > threeSum(vector<int> &nums)
    {
        if (nums.size() < 3)
            return {};
        vector<vector<int> > res;
        set<vector<int> > ret;
        for (int i = 0; i < nums.size() - 2; i++)
        {
            for (int j = i + 1; j < nums.size() - 1; j++)
            {
                for (int k = j + 1; k < nums.size(); k++)
                {
                    if (nums[i] + nums[k] + nums[j] == 0)
                    {
                        vector<int> temp;
                        int a = (nums[i] < nums[j] ? nums[i] : nums[j]) < nums[k] ? (nums[i] < nums[j] ? nums[i] : nums[j]) : nums[k];
                        int b = (nums[i] > nums[j] ? nums[i] : nums[j]) > nums[k] ? (nums[i] > nums[j] ? nums[i] : nums[j]) : nums[k];
                        int c = 0 - a - b;
                        temp.push_back(a);
                        temp.push_back(c);
                        temp.push_back(b);
                        ret.insert(temp);
                    }
                }
            }
        }
        for (auto it : ret)
        {
            res.push_back(it);
        }
        return res;
    }
};
```
