每日一题(LeetCode)----哈希表--三数之和
每日一题(LeetCode)----哈希表–三数之和
1.题目（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 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
2.解题思路
思路一：双指针法
1.我们先把给出的数组进行排序
注意：排序后的数组如果第一个数都大于零，那么没有符合条件的三元组
2.然后每次确定一个数a
对于这个数我们需要去重，我们比较它的前一个数是否和当前数一样，一样的话就说明我们这次的数就算有能满足的三元组也是重复的，所以我们将a的下一位作为新的a
3.再确定另外两个数b和c，我们用两个指针指向确定的第一个数的后一位为b，和给出数组的最后一个数为c
4.（1）如果这三个数的和小于目标和，那么我们把左指针向后移动一位，
（2）如果这三个数的和大于目标值，那么我们把右指针向前移动一位，
（3）如果等于目标和，那么我们将这三个数存入到我们的结果数组中， 然后我们要进行去重， 我们比较左指针的后一个数是否和当前数一样，一样的话就说明我们这次的数就算有能满足的三元组也是重复的，所以我们把左指针向后移动一位，直到左指针后一个数和当前左指针指向的数不一样，左指针所指向的数b去重结束 我们比较右指针的前一个数是否和当前数一样，一样的话就说明我们这次的数就算有能满足的三元组也是重复的，所以我们把右指针向前移动一位，直到右指针前一个数和当前右指针指向的数不一样，右指针所指向的数c去重结束 最后我们把左指针向后移动有一位，把右指针向前移动一位，继续查看是否还有符合条件的三元组
思路来源：代码随想录
链接：代码随想录 (programmercarl.com)
3.写出代码
思路一的代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int length=nums.size();
for(int i=0;i<length;i++){
if(nums[i]>0){
return res;
}
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int left=i+1;
int right=length-1;
while(right>left){
if(nums[i]+nums[left]+nums[right]>0){
right--;
}
else if(nums[i]+nums[left]+nums[right]<0){
left++;
}
else{
res.push_back(vector<int>{nums[i],nums[left],nums[right]});
while(right>left&&nums[right]==nums[right-1]){
right--;
}
while(right>left&&nums[left]==nums[left+1]){
left++;
}
right--;
left++;
}
}
}
return res;
}
};