[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++){//三个元素下标各不相同且相加为0if((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，三个元素之和不可能大于0if(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，三个元素之和不可能大于0if(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;}
};