博客

题目如下

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：


给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[

[-1, 0, 1],

[-1, -1, 2]

]

解题代码

排序+双指针遍历，注意去重即可

vector<vector<int>> threeSum(vector<int> &num)
{
    int len = num.size();
    vector<vector<int>> result;
    result.clear();
    if (len <= 2)
    {
        return result;
    }
    sort(num.begin(), num.end());
    for (int i = 0; i < len - 2; ++i)
    {
        if (num[i] > 0)
        {
            return result;
        }
        if (i > 0 && num[i] == num[i - 1])
        {
            continue;
        }
        int left = i + 1;
        int right = len - 1;
        while (left < right)
        {
            if (num[left] + num[right] + num[i] > 0)
            {
                --right;
            }
            else if (num[left] + num[right] + num[i] < 0)
            {
                ++left;
            }
            else
            {
                result.push_back({num[i], num[left], num[right]});
                while (left < right && num[left] == num[left + 1])
                    ++left;
                while (left < right && num[right] == num[right - 1])
                    --right;
                ++left;
                --right;
            }
        }
    }
    return result;
}