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]
输出：[]

提示：

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

自行解答:

本题难点有2点：1：想到排序 2：去重。再进一步思考其实排序其中一方面的辅助作用也是去重，另一方面可以使用排序之后的数字的顺序进一步找到符合题意的a，b，c

本来先以递归来找符合 题意的数组在去重结果超时了，因此修改成了排序 +双指针移动的方式来实现，满足题意。具体思路如下：

1. 对原数组排序，排成从小到大

2. 遍历数组，根据题意，最外层循环每次的值代表a ，同时需要从第二位起去掉重复值

3. 内层循环，头尾指针分别代表 b和c，同时移动，

   要是头指针 + 尾指针> -a(b+c = -a 决定) ，尾指针--

   要是头指针 + 尾指针< -a(b+c = -a 决定) ，头指针++

4. 头指针 + 尾指针 == -a的时候，将外层循环的a，头指针，尾指针pushback进去，再将这个vector push_back到目标数组中

5. 在条件4的情况下，头指针++，尾指针--，但是头尾指针移动的原则是移动到下一个和当前值不一样的位置

   vector<vector<int>> threeSum(vector<int>& nums) {
         //1：排序 
            sort(nums.begin(), nums.end());
           vector<vector<int>> threeNums;
           vector<int> result;
           for(int i = 0;i<nums.size();i++){
               int first =  nums[i];
             //去除重复的a值
               if(i>=1 &&(nums[i] == nums[i-1])){
                   continue;
               }
               int sum = -first;
               int second= i+1;
               int third = nums.size()-1;
               while (third>second){
                 //3：根据头尾指针和寻找符合 题意的b和c进行定位
                   if(nums[second] + nums[third] >sum){
                       third--;
                       continue;
                   }
                   if(nums[second] + nums[third] <sum){
                       second++;
                       continue;
                   }
                 //4:找到符合题意的b和c
                   if(nums[second] + nums[third] == sum){
                       result.push_back(first);
                       result.push_back(nums[second]);
                       result.push_back(nums[third]);
                       threeNums.push_back(result);
                       result.clear();
                     //5:移动头尾指针，找到下一个不是当前值的头尾指针
                       int j =third-1;
                       while(true){
                           if(nums[third] !=nums[j] || j<=second){
                               third = j;
                               break;
                           }
                           j--;
                       }
                       j = second+1;
                       while (true){
                           if(nums[second] != nums[j] ||j>third){
                               second = j;
                               break;
                           }
                           j++;
                       }
                   }
               }
           }
           return threeNums;
       }
   

复杂度分析：

时间复杂度：O（n2），外层循环n次，内层头尾指针循环和为n，因此时间复杂度是n的平方。注：n为入参nums数组的长度

空间复杂度：O（1），使用了有限的变量，因此空间复杂度为O（1）