[LeetCode]day21 15.三数之和

题目链接

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

解题

审题

注意这道题是需要去重的，可以观察示例1，有两种情况都是0+1+（-1），这两种情况就视为一种

解题

版本一：纯暴力解法

最容易想到的就是用三重循环.

• 找到一个满足条件的数组
• 对其进行排序（假如有两种结果 i,j,k对应的元素分别为1,2，-3，另一种结果对应的元素是-3,1,2,则两个数组{1,2，-3}，{-3,1，2}排序后都是{-3,1，2}，是相同的，方便后面进行去重）
• 判断结果数组中是否有相同的数组，如果没有，加入结果数组中

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    //存放所有可能的结果数组
     vector<vector<int>>result;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums.size();j++){
              for(int z=0;z<nums.size();z++){
                //三个元素下标各不相同且相加为0
                if((nums[i]+nums[j]+nums[z]==0) &&i!=j&&i!=z&&j!=z){
                    //将这三个元素按顺序组成数组
                    vector<int>ans={nums[i],nums[j],nums[z]};
                    //排序
                    sort(ans.begin(),ans.end());
                    int find=false;
                    //如果result里已经有相同的数组，则就不放入了
                   for(int a=0;a<result.size();a++){
                    if(result[a]==ans){
                        find=true;
                        break;
                    }
                   }
                   if(!find)
                    result.push_back(ans);
                }
              }
             }
        }
        return result;

    }
};

测试通过，提交喜提超时

版本二 双指针法

思路分析：

• 排序数组：首先对数组进行排序，以便后续处理。

• 遍历固定一个数：遍历数组中的每个元素作为三元组的第一个数。

• 双指针寻找另外两个数：对于每个固定的数，使用左右指针在剩余数组中寻找另外两个数，使得三个数的和为0。（如果总和<0,left++,总和大于0，right–，总和为0，两个都向中间移动）

• 去重处理：跳过重复的元素，避免生成重复的三元组。

易错点：去重操作
如上面的图，对于下标为i的去重方法和left，right的去重方法有所不同
第一个元素的去重： if(i>0&&nums[i]==nums[i-1])continue;
为什么不是判断nums[i]==nums[i+1]呢？？
如-1，-1,-1，0,1,2
有可能是
（1）i=0,left=1,right=5 (2)i=1,left2,right=5
这两种情况其实是一样的，都是-1+（-1）+2
如果是判断nums[i]==nums[i+1] i就直接移到下标为2的位置上了，有效的三元组就被略过去了
如果是判断nums[i]==nums[i-1]，就可以有效的略过相同的情况
对于第二个第三个元素的去重：
while(nums[right]==nums[right-1]&&left<right) right–;
while(nums[left]==nums[left+1]&&left<right)left++;

看起来都挺抽象的，其实自己画个图试着走一遍流程就能理解了

错误版本

class Solution {
public:
   vector<vector<int>> threeSum(vector<int>& nums) {
   vector<vector<int>>result;
   int left=0,right=0;
   //先对数组进行排序
  sort(nums.begin(),nums.end());
  for(int i=0;i<nums.size();i++){
   if(nums[i]>0)return result; //如果第一个元素大于0，三个元素之和不可能大于0
   if(i>0&&nums[i]==nums[i-1])continue;
   left=i+1;
   right=nums.size()-1;
   while(right>left){
       if(nums[i]+nums[right]+nums[left]>0){
           right--;  
           while(nums[right]==nums[right-1]&&left<right) right--;
       }else if(nums[i]+nums[right]+nums[left]<0){
           left++;
           while(nums[left]==nums[left+1]&&left<right)left++;
       }else{
          result.push_back(vector<int>{nums[i],nums[left],nums[right]});
           //while(nums[right]==nums[right-1]&&left<right) right--;
          // while(nums[left]==nums[left+1]&&left<right)left++;
          left++;
          right--;
       }
   }
  }
  return result;
   }
};

这个版本错误在于去重操作有误 我最开始写的时候 在每一次left和right要移动时，就进行一个去重，会导致数组越界，但需要在找到一个满足条件的结果之后再进行去重

正确版本

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>>result;
    int left=0,right=0;
    //先对数组进行排序
   sort(nums.begin(),nums.end());
   for(int i=0;i<nums.size();i++){
    if(nums[i]>0)return result; //如果第一个元素大于0，三个元素之和不可能大于0
    if(i>0&&nums[i]==nums[i-1])continue;
    left=i+1;
    right=nums.size()-1;
    while(right>left){
        if(nums[i]+nums[right]+nums[left]>0){
            right--;  
        }else if(nums[i]+nums[right]+nums[left]<0){
            left++;
        }else{
           result.push_back(vector<int>{nums[i],nums[left],nums[right]});
            while(nums[right]==nums[right-1]&&left<right) right--;
           while(nums[left]==nums[left+1]&&left<right)left++;
           left++;
           right--;
        }
    }
   }
   return result;
    }
};