15.三数之和(双指针,C解答附详细分析)

发布时间:2024年01月04日

题目描述:

给你一个整数数组?nums?,判断是否存在三元组?[nums[i], nums[j], nums[k]]?满足?i != ji != 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 a>b?1:-1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int base=100;//数组的初始长度,可更改
    //初始化处理返回值,二维数组的大小和保存每一个一维数组大小的数组的空间保持一致
    int** res=(int**)malloc(sizeof(int*)*base);
    *returnColumnSizes=(int*)malloc(sizeof(int)*base);
    *returnSize=0;
    int i,j,k;
    //排序
    qsort(nums,numsSize,sizeof(int),cmp);
    for(i=0;i<numsSize;i++){
        //先确定第三个数的值,再对剩下的两个数进行两数之和的操作
        //若本次的第三个数与上一次的情况相同,则跳过这个数
        if(i>0&&nums[i]==nums[i-1])
            continue;
        //给定nums[i],以j,k作为双指针进行两数之和操作
        j=i+1;
        k=numsSize-1;
        while(j<k){
            int sum=nums[i]+nums[j]+nums[k];
            if(sum==0){//刚好遇见符合要求的三元组
                //申请返回值二维数组的空间
                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(*returnSize==base){
                    base*=2;
                    res=(int**)realloc(res,sizeof(int*)*base);
                    *returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*base);
                }
                //记录符合要求的两个数,进行去重
                int num1=nums[j],num2=nums[k];
                while(nums[j]==num1&&j<k)
                    j++;
                while(nums[k]==num2&&j<k)
                    k--;
            }
            //若三个数之和小于0,则左边的指针右移
            else if(sum<0)
                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博客

文章来源:https://blog.csdn.net/qq_52622503/article/details/135395481
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。