力扣15：三数之和

给你一个包含 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 = []
输出：[]

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

暴力解法的思路是采用两个for循环，先固定两个值，再用find函数去寻找是否有下一个。然后对查找结果进行排序，并且放入hash表中用来去重。但时间复杂度虽然是 O ( n 2 ) O(n^2) O(n2)但由于find函数也会有大量运算，所以递交leetcode的时候会产生运行超时

    //暴力解法
    vector>threeSum(vector&nums)
    {
        vector>numList;
        vectortemplist;
        map,int>hashList;
        //双重for循环然后找到匹配的值然后进行排序
        for(int i=0;i
            for(int j=i+1;j
                int temp=0-nums[i]-nums[j];

                auto res=find(nums.begin()+j+1,nums.end(),temp);

                if(res!=nums.end())
                {
                    templist.clear();
                    templist.push_back(nums[i]);
                    templist.push_back(nums[j]);
                    templist.push_back(temp);
                    sort(templist.begin(),templist.end());
                    hashList.insert(make_pair(templist,i));
                }
            }
        }
    auto index=hashList.begin();
    for(auto i:hashList)
    {
        numList.push_back(i.first);
    }
        return numList;
    }

本题的主流思路是使用双指针方法，判断输入无序，输出有序的情况。首先第一点就是进行先对输入的数组进行排序。再接下来固定第一个字符。剩下的问题便变成了两数之和问题，可参考Leetcode第一题中的描述。本题我们采用双指针的方法，当两数之和大于目标值时，右指针左移，当两数之和小于目标值时，左指针右移。时间复杂度也为 O ( n 2 ) O(n^2) O(n2)

 vector>threeSum2(vector&nums)
    {
        vector>numList;
        int length=nums.size();
        //当输入的字符数量小于3的时候，直接跳出
        if(length<3)
        {
            return numList;
        }
        //对容器进行排序
        sort(nums.begin(),nums.end());
        //固定第一个数，进而转化成求两数之和的问题
        for(int i=0;i
            //当排序后第一个数值的值大于0，肯定接下来都大于0
            if(nums[0]>0)
            {
                return numList;
            }   

            //去重：若当前数被选择过，则跳过
            //continue作用，如果满足if里面的条件，则不执行循环语句中的剩余内容，跳出循环，执行下一次循环
            if(i>0&&nums[i]==nums[i-1])
                continue;
            
            //使用双指针方法
            int left=i+1;
            int right=length-1;
            int tempNum=-nums[i];

            while(left
                //两数之和太小，左指针右移
                if(nums[left]+nums[right]
                    left++;
                }
                //两数之和太大，右指针左移
                else if(nums[left]+nums[right]>tempNum)
                {
                    right--;
                }
                //当找到一个和为零的三元组，添加到结果中，并移动左右指针收缩，继续寻找
                else
                {
                    numList.push_back(vector{nums[i],nums[left],nums[right]});
                    left++;
                    right--;

                    //去重
                    while(left
                        left++;
                    }
                    while(left
                        right--;
                    }
                }
            }
        }
        

        return numList;
    }