网站app免费下载软件大全,湖北微网站建设费用,番禺区网站建设哪家好,怎么做网站报告题目描述
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组…题目描述
给你一个整数数组 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
-10^5 nums[i] 10^5分析思路
这道题跟两数之和一个道理可以用map存储ab的值和出现的次数然后遍历最后一个数组判断c是否等于负的ab。但是此题要求去重因此用map哈希表不方便。
题解中给出了一种双指针的方法。首先对数组进行排序然后for循环遍历i给定两个指针left i1和right i-1如果三数之和大于0则right–小于0则left。
思路比较简单主要是去重的时候需要注意很多的细节看代码随想录的讲解和视频。
这里去重是因为首先对数组进行了排序。i去重的原因是已经将 nums[i - 1] 的所有组合加入到结果中本次双指针搜索只会得到重复组合。 对left去重的原因是去掉所有已经用过的left对right去重的原因是吴吊所有已经用过的right–。
看下力扣k神的讲解和动画也很清楚k神讲解
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;// 排序sort(nums.begin(), nums.end());for(int i0;inums.size();i){if(nums[i]0) break;if(i0 nums[i]nums[i-1]){continue;}int left i1;int right nums.size()-1;while(left right){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(left right nums[right]nums[right-1]) right--;while(left right nums[left]nums[left1]) left;left;right--;}}}return res;}
};
