[数据结构与算法]15.三数之和

想法：

这个题目。让我学到好多东西

首先，<vector>.size()返回unsign int类型！！！不是int类型

第二，&&运算符有短路功能，即A&B中若A为0就不计算B

第三，就是排序加双指针的算法，有点意思

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：
?

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> v;
        vector<int> v1;
        sort(nums.begin(),nums.end());
        int i,x,y,sum;
        //0 0 0 0
        //0 1 2 3
        for(i = 0;i < nums.size();i++)
        {
            x =  i + 1;
            y = nums.size() - 1;
            while(x < y && x < nums.size() && y >= 0)
            {
                sum = nums[i] + nums[x] + nums[y];
                if(sum < 0)
                {
                    while(x + 1 < nums.size() && nums[x + 1] == nums[x])
                    {
                        x++;
                    }
                    x++;
                }
                else if(sum > 0)
                {
                    while(y - 1 >= 0 && nums[y - 1] == nums[y])
                    {
                        y--;
                    }
                    y--;
                }
                else if(sum == 0)
                {
                    v1 = {nums[i],nums[x],nums[y]};
                    v.push_back(v1);
                    while(x + 1 < nums.size() && nums[x + 1] == nums[x])
                    {
                        x++;
                    }
                    x++;
                    while(y - 1 >= 0 && nums[y - 1] == nums[y])
                    {
                        y--;
                    }
                    y--;
                }
            }
            while(i + 1 < nums.size() && nums[i + 1] == nums[i])
            {
                i++;
            }
        }
        return v;
    }
};