直播网站开发秀色,建设工程施工合同范本最新版,手机网站开发成为小程序,wordpress数据库承载给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。 示例 1…给你一个整数数组 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
思路根据题目可知当三个下标互不相同的数相加的和为零时成为三元组所以有abc0当确定其中两个数a,b时可以知道c-(ab);因此使用二重循环遍历数组规定a,b的数值。并在哈希表中判断是否含义需要的数值c有则将a,b,c三个数放入数列中并压入最后的数组序列进行保存。
经过上诉操作可以获得所有满足要求的序列但由于三元组中排列顺序不重要因此需要去除重复将数组进行有序排列当指针i或指针j指向的元素与上一个相同说明在上一轮已经判断过直接跳过即可有效避免重复判断eg:-1,0,1,2,-1,-4 排列后为-4-1-1012 其中-101是一个三元组-1两次出现当i指向第二个-1时由于其上一个也是-1因此跳过对第二个-1的判断
class Solution {
public:vectorvectorint threeSum(vectorint nums) {//将数组存入哈希表中sort(nums.begin(),nums.end());mapint,vectorinttable;for(int i0;inums.size();i){int valuenums[i];//当两个不同下标的数值相同时会错考虑哈希表数列并了解如何遍历一个键对应的值table[value].push_back(i);}//如何保证每次压入的都是当前的三个元素vectorvectorintsolution;for(int i0;inums.size()-1;i){//去除重复if(i0){if(nums[i]nums[i-1])continue; }for(int ji1;jnums.size();j){if(ji1){if(nums[j]nums[j-1])continue; }int need-1*(nums[i]nums[j]);vectorintQ;if(table.find(need)!table.end()){Q table[need];}for(int k0;k Q.size();k){if(Q[k]iQ[k]j){//找到一个三元组vectorintTriplet;Triplet.push_back(nums[i]);Triplet.push_back(nums[j]);Triplet.push_back(need);solution.push_back(Triplet);break;}}}}return solution;}
}; 区分vectorvectorintsolution;和mapint,vectorinttable传入数据的区别都是用push_back()但是第一个使用solution.push_back()而第二个需要指明其键是什么table[need].push_back();
