三数之和

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleSort(int* num, int numLen)
{
    for(int i = numLen - 1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(num[j] > num[j+1])
            {
                swap(&num[j], &num[j+1]);
            }
        }
    }
}

int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if(numLen < 3)
    {
        *returnColumnSizes = 0;
        return NULL;
    }

    //二维指针，指向一块长度numLen * numLen，每个元素都是int*类型的内存
    int** ret = (int **)malloc(sizeof(int *) * numLen * numLen);
    //数组指针，(*returnColumnSizes)[i]存储列元素个数
    *returnColumnSizes = (int *)malloc(sizeof(int) * numLen * numLen);
    int count = 0;

    bubbleSort(num, numLen);

    for(int i = 0; i < numLen - 2; i++)
    {
        if(i != 0 && num[i] == num[i-1]) continue;

        //双指针
        int p1 = i + 1;
        int p2 = numLen - 1;

        while(p1 < p2)
        {
            if(-num[i] == num[p1] + num[p2])
            {
                (*returnColumnSizes)[count] = 3;

                //二维指针的每一个元素指向一块3个int类型的内存
                ret[count] = (int *)malloc(sizeof(int) * 3);
                ret[count][0] = num[i];
                ret[count][1] = num[p1];
                ret[count][2] = num[p2];
                count++;

                while(p1 < p2 && num[p1] == num[p1+1]) p1++;
                while(p1 < p2 && num[p2] == num[p2-1]) p2--;

                p1++;
                p2--;
            }
            else if(-num[i] < num[p1] + num[p2]) p2--;
            else p1++;
        }
    }
    
    *returnSize = count;
    return ret;
}

int cmp(const void*e1,const void*e2)
{
    return *(int*)e1-*(int*)e2;
}
int cmp_1(const void*e1,const void*e2)
{
   int* p1 = *(int**)e1;
   int* p2 = *(int**)e2;
   if(p1[0]>p2[0])
    return 1;
   else if(p1[0] == p2[0] && p1[1]>p2[1])
     return 1;
    else if(p1[0] == p2[0] && p1[1] == p2[1] && p1[2]>p2[2])
     return 1;
    return 0;
}
void swap(int* a ,int* b)
{
    int tmp=*a;
    *a = *b;
    *b = tmp;
}
int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes ) 
{
    // write code here
    if(num==NULL || numLen<3)
        return NULL;
    int l=0,r=numLen;
    int** ret = malloc(sizeof(int*)*1000);
    *returnColumnSizes = malloc(sizeof(int)*1000);
	int* arr = malloc(sizeof(int)*numLen);
    int idx = 0;
    while(l<r)
    {
		memcpy(arr,num,sizeof(int)*numLen);
        swap(&num[0],&num[l]);
		qsort(num+1, numLen-1, sizeof(num[0]),cmp);
        int start = 1,end = numLen-1,target = 0-num[0];
        while(start<end)
        {
            if(num[start]+num[end]>target)
                end--;
            else if(num[start]+num[end]<target)
                start++;
            else
            {   
                int* tmp = malloc(sizeof(int)*3);
                tmp[0] = num[0];
                tmp[1] = num[start];
                tmp[2] = num[end]; 
                qsort(tmp, 3, sizeof(tmp[0]),cmp);
				int j =0,flag= 0;
				for(j=0;j<idx;j++){
					if(tmp[0]==ret[j][0] && tmp[1]==ret[j][1] && tmp[2]==ret[j][2])
					{	
						flag = 1;
						break;
					}
				}
				if(flag)
				{
					start++;
					end--;
					continue;
				}
                (*returnColumnSizes)[idx] = 3;
                ret[idx++] = tmp;
				start++;
				end--;
            };
        }
      	memcpy(num,arr,sizeof(int)*numLen);
        l++;
    }
    *returnSize = idx;
    qsort(ret, idx, sizeof(int*),cmp_1);
    return ret;
}