LeetCode第15题: threeSum(C语言)

2019-07-14  本文已影响0人  闫品品

上一题:LeetCode第14题: longestCommonPrefix(C语言)

求助:本地运行没问题,但是在LeetCode中就报错,而且是快速排序出错,原因应该是快排里面用了递归,内存占用大

int main(int argc, const char * argv[]) {

    int nums[6]={-1,0,1,2,-1,-4};
    int *q;
    q=nums;
    int numsSize=6;
    int* returnSize;
    int **p;
    returnSize=(int*)malloc(sizeof(int*));
    p=(int**)malloc(sizeof(int*)*(numsSize*(numsSize-1)*(numsSize-2))/6);
    threeSum(nums,numsSize,returnSize, p);
    for(int i=0;i<*returnSize;i++)
    {
        int *num = p[i];
        for(int j=0;j<3;j++)
        {
            printf("%d ",num[j]);
        }
        printf("\n");
        
    }
    
    return 0;
}

void quickSort(int *nums, int left, int right){
    int i, j, pivot, temp;
    if(left < right){
        i = left;
        j = right + 1;
        pivot = nums[left];
        do{
            do{
                i++;
            }while(nums[i] < pivot);
            do{
                j--;
            }while(nums[j] > pivot);
            if(i < j){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }while(i < j);
        temp = nums[left];
        nums[left] = nums[j];
        nums[j] = temp;
        
        quickSort(nums, left, j - 1);
        quickSort(nums, j + 1, right);
    }
}
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    quickSort(nums, 0, numsSize - 1);
    int index = 0;
    int start = 0;
    int end = numsSize - 1;
    int sum = 0;
//    returnSize = (int *)malloc(sizeof(int));
//    returnColumnSizes = (int **)malloc((numsSize * (numsSize - 1) * (numsSize - 2) / 6 )* sizeof(int *));
    for(int i = 0; i < numsSize; i++){
        if(nums[i] > 0)
            break;
        if(i > 0 && nums[i] == nums[i - 1])
            continue;
        start = i + 1;
        end = numsSize - 1;
        while(start < end){
            sum = nums[i] + nums[start] + nums[end];
            if(sum == 0){
                returnColumnSizes[index] = (int *)malloc(3 * sizeof(int));
                returnColumnSizes[index][0] = nums[i];
                returnColumnSizes[index][1] = nums[start];
                returnColumnSizes[index][2] = nums[end];
                start++;
                end--;
                while(start < end && nums[start] == nums[start - 1])
                    start++;
                while(start < end && nums[end] == nums[end + 1])
                    end--;
                index++;
            }
            else if(sum > 0)
                end--;
            else
                start++;
        }
    }
    *returnSize = index;
    return returnColumnSizes;
}

本系列文章,旨在打造LeetCode题目解题方法,帮助和引导同学们开阔学习算法思路,由于个人能力和精力的局限性,也会参考其他网站的代码和思路,如有侵权,请联系本人删除。
下一题:LeetCode第16题: threeSumClosest(C语言)

上一篇下一篇

猜你喜欢

热点阅读