哈尔滨教育云平台网站建设,物联网工程就业方向及前景,做网站建设的平台,新野微网站建设题目#xff1a; 给你一个整数数组 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 。 思路 逐个遍历数组确定第一个元素后剩下的两个数字就是和为 target - nums[i] 的两个数字了因此将确定元素的下一个索引和target-nums[i]传给两个数相加和为某个数的函数由该函数返回所有满足和为target-nums[i]的二维vector将返回的结果遍历如果结果不为空每次循环将刚在确定的第一个数加进这个一维vector中组成一个和为0的三元组再将这个三元组加入到vector中在最后需要跳过第一个数组重复的情况否则可能会出现重复的结果。 vectorvectorint twoSumtarget(vectorint nums,int start,int target) {int left start;int right nums.size() - 1;vectorvectorint res;while (leftright) {int leftnum nums[left];int rightnum nums[right];int sum nums[left] nums[right];if (sum target) {while (left rightnums[left] leftnum) {left;}}else if (sum target) {while (left right nums[right] rightnum) {right--;}}else if(sum target){res.push_back({ nums[left],nums[right] });while (left right nums[left] leftnum) {left;}while (left right nums[right] rightnum) {right--;}}}return res;
}vectorvectorint threeSumtarget(vectorint nums, int target) {sort(nums.begin(),nums.end());int numsize nums.size();vectorvectorint res;for (int i 0; i numsize;i) {vectorvectorint tuples twoSumtarget(nums,i1,target-nums[i]);//如果存在满足条件的二元组再加上nums[i]结果就是三元组for (vectorint tuple:tuples) {tuple.push_back(nums[i]);res.push_back(tuple);}//跳过第一个数字重复的情况否则可能会出现重复结果while (i numsize - 1 nums[i] nums[i 1]) i;}return res;
}int main() {vectorint c{ -1,0,1,2,-1,4 };int target 0;vectorvectorint result threeSumtarget(c,target);for (vectorvectorint::iterator it result.begin(); it ! result.end();it) {for (vectorint::iterator pit (*it).begin(); pit ! (*it).end();pit) {cout*pit ;}cout endl;}return 0;
}
