每日一题(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;}
};