旅游网站的建设现状,苏州市城乡建设局网站首页,齐河专业企业网站建设,北京公司注册地址要求给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
答案中不可以包含重复的三元组。
示例 1#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] 。
解析
先对数组排序设一非递减的数组示例和初始三指针位置及名字如下所示。 固定i即可转换为寻找满足 nums[l]nums[r]−nums[i] 的三元组因为不能包含重复的三元组以下两个三元组只能取一个而后我们再考虑其是否满足 nums[l]nums[r]−nums[i]。 移动指针的时候需要规避连续的重复元素
class Solution {
public:vectorvectorint threeSum(vectorint nums) {//排序c// 待返回的三元组vectorvectorint triples;for(int i 0; i nums.size(); i){// 检测重复的 nums[i]if(i 0 nums[i] nums[i-1]) continue;int l i 1;int r nums.size() - 1;while(l r) {// 检测重复的 nums[l] 并防止越界while(l i 1 l nums.size() nums[l] nums[l-1]) l;// 检测重复的 nums[r] 并防止越界while(r nums.size() - 1 r i nums[r] nums[r1]) r--;// 防止 l, r 错位if(l r) break;if(nums[i] nums[l] nums[r] 0) r--;else if(nums[i] nums[l] nums[r] 0) l;else {// nums[l] nums[r] nums[i], 三元组符合添加入结果triples.push_back({nums[i], nums[l], nums[r]});l; r--;}}}return triples;}
};
int cmp(const void* pa, const void* pb){int a*(int*)pa;int b*(int*)pb;return ab?1:-1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int base100;//数组的初始长度可更改//初始化处理返回值二维数组的大小和保存每一个一维数组大小的数组的空间保持一致int** res(int**)malloc(sizeof(int*)*base);*returnColumnSizes(int*)malloc(sizeof(int)*base);*returnSize0;int i,j,k;//排序qsort(nums,numsSize,sizeof(int),cmp);for(i0;inumsSize;i){//先确定第三个数的值再对剩下的两个数进行两数之和的操作//若本次的第三个数与上一次的情况相同则跳过这个数if(i0nums[i]nums[i-1])continue;//给定nums[i]以jk作为双指针进行两数之和操作ji1;knumsSize-1;while(jk){int sumnums[i]nums[j]nums[k];if(sum0){//刚好遇见符合要求的三元组//申请返回值二维数组的空间res[*returnSize](int*)malloc(sizeof(int)*3);//每一个数组大小都为3(*returnColumnSizes)[*returnSize]3;//给申请的空间赋值res[*returnSize][0]nums[i];res[*returnSize][1]nums[j];res[*returnSize][2]nums[k];//二维数组的行数加1(*returnSize);//如果二维数组的大小达到初始设定的行数则进行空间扩容if(*returnSizebase){base*2;res(int**)realloc(res,sizeof(int*)*base);*returnColumnSizes(int*)realloc(*returnColumnSizes,sizeof(int)*base);}//记录符合要求的两个数进行去重int num1nums[j],num2nums[k];while(nums[j]num1jk)j;while(nums[k]num2jk)k--;}//若三个数之和小于0则左边的指针右移else if(sum0)j;//若三个数的之和大于0则右边的指针往左移else k--;}}return res;
}
