leetcode-4sum

 typedef struct Element{
    int val; //sum of two numbers
    int idx_l; //less number's index
    int idx_g; //bigger number's index
} Ele;
int cmp(const void *a,const void *b){
    return ((Ele *)a)->val-((Ele *)b)->val;
}
int cmp_int(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    int **ret=NULL;
    int sum_size=numsSize*(numsSize-1)/2;
    Ele* sum_of_two=(Ele*)malloc(sum_size*sizeof(Ele));
    int i,j,k=0;
    *returnSize=0;
    qsort(nums,numsSize,sizeof(nums[0]),cmp_int);
    for(i=0;i<numsSize;i++)
        for(j=i+1;j<numsSize;j++){
            sum_of_two[k].val=nums[i]+nums[j];
            sum_of_two[k].idx_l=i;
            sum_of_two[k].idx_g=j;
            k++;
        }
    qsort(sum_of_two,sum_size,sizeof(Ele),cmp);
    for(i=0;i<numsSize-1;i++){
        for(j=i+1;j<numsSize;j++){
            int left=0,right=sum_size-1,mid;
            while(left<right){
                mid=(left+right)/2;
                if((nums[i]+nums[j]+sum_of_two[mid].val==target)){
                    int sa,p=mid,sp;
                    while(sum_of_two[mid].val==sum_of_two[p].val&&p>=0) p--;
                    sa=(p>=0?++p:0);
                    p=mid;
                    while(sum_of_two[mid].val==sum_of_two[p].val&&p<sum_size) p++;
                    sp=p;
                    for(mid=sa;mid<sp;mid++){
                        //printf("%d:%d=>%d\t%d\t%d\n",i,j,nums[i],nums[j],sum_of_two[mid].val);
                        if(sum_of_two[mid].idx_l!=i&&sum_of_two[mid].idx_g!=j&&sum_of_two[mid].idx_l!=j&&sum_of_two[mid].idx_g!=i){
                            int tmp[4];
                            tmp[0]=nums[i];
                            tmp[1]=nums[j];
                            tmp[2]=nums[sum_of_two[mid].idx_l];
                            tmp[3]=nums[sum_of_two[mid].idx_g];
                            qsort(tmp,4,sizeof(int),cmp_int);
                            for(k=0;k<*returnSize;k++){
                                if(tmp[0]==ret[k][0] && tmp[1]==ret[k][1] && tmp[2]==ret[k][2]) {
                                    break;
                                }
                            }
                            if(k==*returnSize){
                                ret=(int **)realloc(ret,sizeof(int*) * ((*returnSize)+1));
                                int *row=(int*)malloc(sizeof(int)*4);
                                row[0]=nums[i];row[1]=nums[j];row[2]=nums[sum_of_two[mid].idx_l];row[3]=nums[sum_of_two[mid].idx_g];
                                qsort(row,4,sizeof(int),cmp_int);
                                ret[*returnSize]=row;
                                (*returnSize)++;
                            }
                        }
                    }
                    break;
                }
                if(sum_of_two[mid].val<(target-nums[i]-nums[j])){
                    left=mid+1;
                }
                if(sum_of_two[mid].val>(target-nums[i]-nums[j])){
                    right=mid-1;
                }
            }
        }
        
    }
    return ret;
}