题解 | #三数之和#

C语言

//从小排到大
void sort(int *num, int numLen){
    int temp;
    for(int i=0; i<numLen; i++){
        for(int j=i; j<numLen; j++){
            if(num[j] < num[i]){
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }
}

int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int a,bindex,cindex;
    int** retArray = (int**)malloc(sizeof(int*)*numLen*numLen);    
    *returnColumnSizes = (int*)malloc(sizeof(int)*numLen*numLen);   
    // int (*retColSize)[1] =  (int (*)[1])returnColumnSizes;   //该参数一直调不过
    // int retArray[5][3] = {0};       //本地测试
    sort(num, numLen);
    for(int i=0; i<numLen; i++){//从数组头开始遍历a
        a = num[i];             
        bindex = i+1, cindex = numLen-1;    //更新bc索引
        if(a>0)break;               //如果a大于0，此时由于已经升序排列，bc不满足+a等于0，退出循环 
        //双指针
        while(bindex < cindex){     //如果左指针b 大于 右指针c， 则退出
            if(a*(-1) < (num[bindex] + num[cindex]))            //-a < b+c :大边缩小
                cindex--;
            else if(a*(-1) > (num[bindex] + num[cindex]))       //-a > b+c: 小边增大
                bindex++;
            else{                                               //-a = b+c
                retArray[(*returnSize)] = (int*)malloc(sizeof(int)*3);  //动态申请装该结果的空间
                // *(*(returnColumnSizes+(*returnSize))) = 3;
                (*returnColumnSizes)[(*returnSize)] = 3;
                retArray[(*returnSize)][0] = a;                 //将abc装入返回数组，此时已经是升序排列
                retArray[(*returnSize)][1] = num[bindex];
                retArray[(*returnSize)][2] = num[cindex];
                (*returnSize)++;                                //返回数组行数+1
                while(num[cindex] == num[cindex-1])             //如果大边多个元素连续相同，跳到上一个不同元素
                    cindex--;
                cindex--;
            }
        }
        //如果有多个元素连续相同，直接跳到下一个不同元素
        while(a == num[i+1])
            i++;
    }
    // for(int i=0; i<(*returnSize); i++)
    //     printf("\r\n ret[%d]: %d %d %d", i, retArray[i][0], retArray[i][1], retArray[i][2]);
    return retArray;
}