C++ 三数之和

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

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

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = [0,1,1]
输出：[]

输入：nums = [0,0,0]
输出：[[0,0,0]]

回溯算法，线性遍历所有的可能结果，并判断是否符合条件即可，但是时间复杂度过高。

class Solution {
public:
    void TrackBack(vector& nums,vector>& res,int start,int curRes,vector& back,vector &visited)
    {
        if(back.size() == 3)
        {
            if(curRes == 0)
                res.push_back(back);
            return;
        }

        for(int i = start;i < nums.size();i++)
        {
            if(i > 0 && nums[i] == nums[i -1] && visited[i-1] == 0)
                continue;
            back.push_back(nums[i]);
            curRes += nums[i];
            visited[i] = 1;
            TrackBack(nums,res,i + 1,curRes,back,visited);
            back.pop_back();
            curRes -= nums[i];
            visited[i] = 0;
        }
    }


    vector> threeSum(vector& nums) 
    {
        vector> arrs;
        vector back;
        vector visited(nums.size(),0);
        std::sort(nums.begin(),nums.end());
        TrackBack(nums,arrs,0,0,back,visited);
        return arrs;
    }
};

构建两数相加事件（两数相加使用二分法-双指针），遍历一次给定数组，使每一个元素均与其后面所有元素的相加情况进行比较，看是否等于0即可。

TIPS：

在这个过程中需要考虑元素相同的情况，该情况下结果需要剔除。

class Solution {
public:
    void TwoSum(vector& nums,int begin,int end,int target,int value,vector>& res)
    {
        int sum = 0;
        while(begin < end)
        {
            sum = nums[begin] + nums[end];
            if(sum == target)
            {
                vector tmp;
                tmp.push_back(nums[begin]);
                tmp.push_back(nums[end]);
                tmp.push_back(value);

                res.push_back(tmp);
                //排除相同的结果
                while(begin < end && nums[begin] == nums[begin+ 1])
                    begin++;
                begin++;
                //排除相同的结果
                while(begin < end && nums[end] == nums[end - 1])
                    end--;
                end--;
            }
            else if(sum < target)
                begin++;
            else
                end--;
        }
    }


    vector> threeSum(vector& nums) 
    {
        vector> arrs;
        std::sort(nums.begin(),nums.end());
        int size = nums.size();
        for(int i = 0;i < size;i++)
        {
            //排除相同的结果
            if(i > 0 && nums[i] == nums[i - 1])
                continue;
            vector> tmp;
            TwoSum(nums, i + 1, size - 1, -nums[i], nums[i], tmp);
            arrs.insert(arrs.end(),tmp.begin(),tmp.end());
        }
        return arrs;
    }
};

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105