网站服务器放在哪里好,四川省建设人才网,装修公司怎么做网站推广,番禺网站建设培训班每日一题(LeetCode)----哈希表–三数之和
1.题目#xff08;15. 三数之和#xff09; 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所…每日一题(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:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(),nums.end());int lengthnums.size();for(int i0;ilength;i){if(nums[i]0){return res;}if(i0nums[i]nums[i-1]){continue;}int lefti1;int rightlength-1;while(rightleft){if(nums[i]nums[left]nums[right]0){right--;}else if(nums[i]nums[left]nums[right]0){left;}else{res.push_back(vectorint{nums[i],nums[left],nums[right]});while(rightleftnums[right]nums[right-1]){right--;}while(rightleftnums[left]nums[left1]){left;}right--;left;}}}return res;}
};
