佛山外贸网站建站,宣传片企业拍摄公司,可以设计房子布局的软件,郑州产品设计公司题目描述#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 。 优秀解答
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;
}解答来自用户烟火
分析本题用C语言实在复杂涉及到二维数组的空间分配有很多细节需要注意。
1.区分指针指针的值指向指针的指针。 本题中res是一个二维数组为指向int指针的指针可以理解为一个元素为int指针的一维数组。由于题解写在函数里函数内部定义的变量都属局部变量而return只能返回一个参数所以用指针returnSize返回三元组的个数。 用指向指针的指针returnColumnSizes返回每一行数组的长度。非常绕多想一想原作者给出的解释为“而在三数之和中要求我们返回的其实是一个二维数组那么我们除了需要知道二维数组的行数每一行的数组的长度也是需要返回的这就是另一个参数int** returnColSize 的用途至于为什么这里也是一个指向指针的指针因为returnColSize是我们从外部传进来的一个指针参数要想保证在函数中对该指针的改变对外部产生影响那么我们在外部传入的时候也应该按照传引用的方式传入一个指针的地址反映到函数中就是一个指向指针的指针。” returnSize作为一个int类型的指针*returnSize为指针指向的值即一个int值可以用res[*returnSize]索引二维数组的行。还需要注意增加三元组个数时(*returnSize);的括号如果不加括号则成了使指针值递增而不是使指针指向的int元素递增。 总结一下res是一个指向指针的指针指向存储答案的二维数组其中每一个符合要求的三元组为一行returnColumnSizes是一个指针指向存储了每行大小本题固定为3的一维数组returnSize是一个指针指向三元组的个数即二维数组的行数。
2.C语言中未知大小数组的空间分配。 C语言中的数组分配必须要有固定大小给解题增加了难度。本题作者定义了一个初始大小base进行空间分配在每次循环中都要比较当前三元组个数是否超过了分配的大小如果空间不够用增加base大小调用realloc(res,sizeof(int*)*base);在原来的基础上增加分配空间。以此实现变长数组。malloc分配空间realloc增加空间calloc分配初始化为0的空间。
3.解题思路分析。 先通过排序使数组有序再依次遍历数组元素 i 对于每个 i 定义 j 初始指向剩余元素中的最小元素定义 k 初始指向剩余元素中的最大元素若三者和小于0则将 j 右移使得新的三数和更大更有机会满足要求否则 k 右移。这是双指针移动的一种基本思路与题目11.盛水最多的容器相同 j 和 k 都不走回头路使得二者移动的步数加起来为n而若用暴力解的双层for循环则为n平方。故本题的解题思路可以理解为进行了n次11题的循环。
相关题目链接11.盛水最多的容器双指针C解法-CSDN博客
