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语言)