題目

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]
]

分析：

這個題的思想和尋找三個數(shù)相加是相同的行施，先確定兩個數(shù)璧榄，然后對剩下的兩個數(shù)從首尾依次尋找册踩，直至找到合適的施禾。
當(dāng)然數(shù)組需要先排序拗胜。如果相同的四元組表制，就不能添加到結(jié)果中撩炊，并且free掉相關(guān)的內(nèi)存

/**
 * 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)/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個組了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
     
    while(i < j)                               /*控制在當(dāng)組內(nèi)尋找一遍*/
    {
        while(i < j && key <= a[j])
        /*而尋找結(jié)束的條件就是放仗，1抑党，找到一個小于或者大于key的數(shù)（大于或小于取決于你想升
        序還是降序）2包警，沒有符合條件1的，并且i與j的大小沒有反轉(zhuǎn)*/ 
        {
            j--;/*向前尋找*/
        }
         
        a[i] = a[j];
        /*找到一個這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是
        a[left]底靠，那么就是給key）*/
         
        while(i < j && key >= a[i])
        /*這是i在當(dāng)組內(nèi)向前尋找害晦，同上，不過注意與key的大小關(guān)系停止循環(huán)和上面相反暑中，
        因為排序思想是把數(shù)往兩邊扔壹瘟，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
    sort(a, left, i - 1);/*最后用同樣的方式對分出來的左邊的小組進(jìn)行同上的做法*/
    sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進(jìn)行同上的做法*/
                       /*當(dāng)然最后可能會出現(xiàn)很多分左右，直到每一組的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;
}