题解 | #三数之和#

 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void quickSort(int *arr ,int left ,int right)
{
    if(left>right)return;
    int temp=arr[left];
    int i=left;
    int j=right;
    while(i<j)
    {
        while(arr[j]>=temp&&i<j){j--;}
        while(arr[i]<=temp&&i<j){i++;}
        if(i<j)
        {
            int t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
    }
    arr[left]=arr[i];
    arr[i]=temp;
    
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}

int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes )
{
//     write code here
    int index_b,index_c;
    int **num_return;
    int count_return=0;
    
    if(numLen<3)
    {
        num_return=(int **)malloc(1*sizeof(int*));
        num_return[0]=(int *)malloc(1*sizeof(int));
        num_return[0][0]=0;
    }
    
    num_return=(int **)malloc(numLen*numLen*sizeof(int*));//一般从函数内部返回二重数组，必须使用二级指针的形式
    *returnColumnSizes = (int *)malloc(numLen*numLen*sizeof(int));//returnColumnSizes是指向int的指针的指针
    //(*returnColumnSizes)[count_return]的值代表第count_return行的列数
    //最多大概有numLen*numLen个解
    quickSort(num, 0, numLen-1);
    for(int index_a=0;index_a<numLen-2;index_a++)
    {
        if(index_a>0&&num[index_a]==num[index_a-1])continue;//这里过滤了含000的情况，不进入while的情况下就能输出000
        index_b=index_a+1;
        index_c=numLen-1;
        while(index_b<index_c)
        {
            printf("%d %d %d\n",num[index_a],num[index_b],num[index_c]);
            if(num[index_b]+num[index_c]==(-num[index_a]))
            {
                num_return[count_return]=(int *)malloc(3*sizeof(int));
                num_return[count_return][0]=num[index_a];
                num_return[count_return][1]=num[index_b];
                num_return[count_return][2]=num[index_c];
                (*returnColumnSizes)[count_return]=3;//这里必须加括号，因为是数组指针
//                 这里每个(*returnColumnSizes)实际上只有一个单位int，因为列数为1
                while(index_b<index_c&&num[index_b]==num[++index_b]);
                while(index_b<index_c&&num[index_c]==num[--index_c]);
                count_return++;
//                 过滤同解且打破和等于0现状，防止死循环，防止a不变时不继续找其他解
//                 break;不能用，可能同一个a对应多组b值
            }
            else if(num[index_b]+num[index_c]<(-num[index_a]))
            {
                index_b++;
            }
            else if(num[index_b]+num[index_c]>(-num[index_a]))
            {
                index_c--;
            }
        }
    }
    *returnSize=count_return;
    return num_return;
}