15. 三数之和

给你一个包含 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题相对来说还是有点难度的，一开始最简单的方法就是暴力，那么有一个问题就是会有重复的结果，所以直接暴力反而麻烦，稍微优化一下就是先排序，排序之后，三层循环，一个个的判断是否和为0，如果是与上一次判断相同的数据，就跳过，这样保证了唯一，思路也简单。

但是提交答案应该会碰到时间超过限制的示例，这个示例中提供了3000个数字，3层循环的话确实耗时比较多，这时需要进一步优化。

怎么优化呢？使用双指针，第一个数字是从左往右遍历，第二个数字是第一个数字的后一位，第三个数字就是从最后一个开始遍历，就算去掉一些特殊情况，这还是3层循环。这里我们并没有把排序的条件用进来，我们只用了排序后的唯一性，并没有用排序后的顺序性，这样肯定就有浪费性能重复的地方，举个例子，字符长度是len，这时候第一个数字索引到了a，第二个数字所以是b，第三个数字索引是c(len-1)，c从最后向左移动，直到遇到相加为0或者相加小于0的索引位置为cx（cxb，所以a+bx+cn(cx

这样优化下来，最外层循环还是n，从第二层循环开始，第二层由左向右，第三层由右向做，并且是延续上一次判断结束的结果，那么就相当于这两层循环是n，就少了一次n的时间复杂度。

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> vvret;
        int len = nums.size();
        if(len >= 3)
        {
            sort(nums.begin(), nums.end());
            for(int i = 0; i < len - 2; i++)
            {
                if(nums[i] > 0)
                {
                    break;
                }
                if(i > 0 && nums[i] == nums[i-1])
                {
                    continue;
                }
                //其他的判断都是点缀，最重要的是这个地方，要把第三层的索引k在这个地方赋值，保证沿用上一次的结果，避免重复判断
                int k = len - 1;
                for(int j = i + 1; j < len - 1; j++)
                {
                    if(j > i + 1 && nums[j] == nums[j-1])
                    {
                        continue;
                    }
                    if(nums[i] + nums[j] + nums[len - 1] < 0)
                    {
                        continue;
                    }
                    if(j+1 < len && nums[i] + nums[j] + nums[j+1] > 0)
                    {
                        continue;
                    }
                    
                    for(; k > j; k--)
                    {
                        if(k < len - 1 && nums[k] == nums[k+1])
                        {
                            continue;
                        }
                        if(j+1 0)
                        {
                            break;
                        }
                        int tnum = nums[i] + nums[j] + nums[k];
                        if(tnum == 0)
                        {
                            vvret.push_back({nums[i], nums[j], nums[k]});
                            break;
                        }
                        else if(tnum < 0)
                        {
                            break;
                        }
                    }
                }
            }
        }
        return vvret;
    }
};