/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}
int** threeSum(int* num, int numsSize, int* returnSize) {
        qsort(num,numsSize,sizeof(num[0]),cmp);
        int** ret=NULL; int ret_size=0;
        for(int i=0; i<numsSize; i++)
        {
            if (num[i]>0)
                break;
            if (i > 0 && num[i]==num[i-1])
                continue;
                 
            int j,k;
            j = i+1;
            k = numsSize-1;
            while (j<k) {
                if (j>i+1 && num[j]==num[j-1]) { 
                    j++;                    
                    continue;
                }
                if (k<numsSize-1 && num[k]==num[k+1]) {
                    k--;
                    continue;
                }
                int sum = num[i] + num[j] + num[k];
                if (sum>0) {
                    k--;
                }else if (sum<0) {
                    j++;
                }else {
                    int* tmp=(int*)malloc(3*sizeof(int));
                    if(ret==NULL){
                        ret=(int **)malloc((ret_size+1)*sizeof(int*));
                    }else{
                        ret=(int **)realloc(ret,(ret_size+1)*sizeof(int*));
                    }
                    tmp[0]=num[i];tmp[1]=num[j];tmp[2]=num[k];
                    ret[ret_size]=tmp;
                    ret_size++;
                    j++;
                }
            }
        }
        *returnSize=ret_size;
        return ret;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据