象递归那样, 划分成2SUM + num[i]的问题求解 C Solution


  • 0
    T
    int cnt = 0;
    
    int comp(const void *n1, void *n2)
    {
        int *num1 = (int *)n1;
        int *num2 = (int *)n2;
        return *num1 > *num2 ? 1 : 0;
    }
    
    int** threeSum(int* nums, int numsSize, int* returnSize) 
    {
        cnt = 0;
        //首先对数组nums进行排序
        qsort(nums, numsSize, sizeof(int), comp);
        //定义返回的二维数组
        int **dp = (int **)malloc(1000000 * sizeof(int *));
    
        //2Sum + 1Sum
        int sum = 0;                        //三个数的和
        for(int i = 0; i < numsSize; i++)
        {
            //判断当前值和下一个值是否相等, 相等就跳过
            if(i > 0 && nums[i] == nums[i-1])
            {
                continue;
            }
            int *pstart = nums + i + 1;
            int *pend = nums + numsSize - 1;
            while(pstart < pend)
            {
                if(*pstart + *pend > sum - nums[i])
                {
                    pend--;
                }
                else if(*pstart + *pend < sum - nums[i])
                {
                    pstart++;
                }
                else if(*pstart + *pend == sum - nums[i])
                {
                    //printf("%d, %d, %d\n", nums[i], *pstart, *pend);
                    int *px = (int *)malloc(3 * sizeof(int));
                    memset(px, 0, 3 * sizeof(int));
                    px[0] = nums[i];
                    px[1] = *pstart;
                    px[2] = *pend;
                    dp[cnt++] = px;
                    while(*pstart == *(pstart + 1))
                    {
                        pstart++;
                    }
                    pstart++;
                   
                    while(*pend == *(pend - 1))
                    {
                        pend--;
                    }
                    pend--;
                   
                    //pstart++;
                    //pend--;
                }
                
            }
        }
        *returnSize = cnt;
        return dp;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.