18四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

双重循环+双指针
时间复杂度O(n^3)
执行用时：56 ms
内存消耗：8.5 MB

int comp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes)
{

    int MAX_RETURN_SIZE = numsSize * numsSize;
    *returnSize = 0;
    *returnColumnSizes = malloc(sizeof(int) * MAX_RETURN_SIZE);
    int **result = malloc(sizeof(int *) * MAX_RETURN_SIZE);
    int *arr;
    int i = 0, j = 0, k = 0, n = 0;
    qsort(nums, numsSize, sizeof(int), comp);
    for (n = 0; n < numsSize; n++)
    {
        if (n > 0 && nums[n] == nums[n - 1])
            continue;
        for (i = n + 1; i < numsSize; i++)
        {
            if (i > n + 1 && nums[i] == nums[i - 1])
                continue;
            j = i + 1;
            k = numsSize - 1;
            while (j < k)
            {
                if (nums[n] + nums[i] + nums[j] + nums[k] < target)
                    j++;
                else if (nums[n] + nums[i] + nums[j] + nums[k] > target)
                    k--;
                else //(nums[n]+nums[i]+nums[j]+nums[k] == target)
                {
                    arr = malloc(4 * sizeof(int));
                    arr[0] = nums[n];
                    arr[1] = nums[i];
                    arr[2] = nums[j];
                    arr[3] = nums[k];
                    (*returnColumnSizes)[*returnSize] = 4;
                    result[(*returnSize)++] = arr;
                    while (j < k && nums[j + 1] == nums[j++])
                        ;
                    while (j < k && nums[k - 1] == nums[k--])
                        ;
                }
            }
        }
    }
    return result;
}