题目

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

分析：

这个题的思想和寻找三个数相加是相同的，先确定两个数，然后对剩下的两个数从首尾依次寻找，直至找到合适的。
当然数组需要先排序。如果相同的四元组，就不能添加到结果中，并且free掉相关的内存

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
     
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
         
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
         
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    int** ans=(int **)malloc(sizeof(int *)*100000);
    *returnSize=0;
    sort(nums,0,numsSize-1);
    for(int i=0;i<numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            int p=j+1,q=numsSize-1;
            while(p<q)
            {
                if(nums[i]+nums[j]+nums[p]+nums[q]<target)
                    p++;
                else if(nums[i]+nums[j]+nums[p]+nums[q]>target)
                    q--;
                else if(nums[i]+nums[j]+nums[p]+nums[q]==target)
                {
                    int *temp=(int *)malloc(sizeof(int)*4);
                    temp[0]=nums[i];
                    temp[1]=nums[j];
                    temp[2]=nums[p];
                    temp[3]=nums[q];
                    sort(temp,0,3);
                    int k=0;
                    for(k=0;k<*returnSize;k++)
                    {
                        if(ans[k][0]==temp[0]&&ans[k][1]==temp[1]&&ans[k][2]==temp[2]&&ans[k][3]==temp[3])
                            break;
                    }
                    if(k==*returnSize)
                    {
                        ans[*returnSize]=temp;
                        *returnSize=*returnSize+1;
                    }
                    else
                        free(temp);
                    p++;
                }
            }
        }
    }
    //printf("%d\n",*returnSize);
    return ans;
}