找到四个，其总和等于目标

Question

问题：
给定一个由 n 个整数组成的数组 nums，返回所有唯一四元组 [nums[a], nums[b], nums[c], nums[d]] 的数组，使得：

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

您可以按任何顺序返回答案。

示例1：

输入：nums = [1,0,-1,0,-2,2]，目标 = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例2：

输入：nums = [2,2,2,2,2]，目标 = 8 输出：[[2,2,2,2]]
限制：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

算法：

1. 首先我们对数组进行排序；
2. 选择三个不同的数字；
3. 找到第四个数字，它必须等于

   target - num1 - num2 - num3

.

C代码：

int partition (int *arr, int left, int right) {
    int x = arr[right];
    int i, j;
    i = left - 1;
    for (j = left; j < right; j++)
        if (arr[j] <= x) {
            int tmp = arr[++i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    arr[right] = arr[++i];
    arr[i] = x;
    return i;
}

void quicksort (int *arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quicksort(arr, left, pivot - 1);
        quicksort(arr, pivot + 1, right);
    }
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    (*returnSize) = 0;
    int **ans = NULL;
    quicksort(nums, 0, numsSize - 1);
    for (int i = 0; i < numsSize - 3; i++)
        for (int j = i + 1; j < numsSize - 2; j++)
            for (int k = j + 1; k < numsSize - 1; k++) {
                int l = target - nums[i] - nums[j] - nums[k];
                int left = k, mid, right = numsSize;
                while (left < right ) {
                    mid = (left + right) / 2;
                    if (nums[mid] < l)
                        left = mid;
                    else if (nums[mid] == l) {
                        (*returnSize)++;
                        ans = realloc(ans, (*returnSize) * sizeof(int));
                        ans[*returnSize - 1][0] = nums[i];
                        ans[*returnSize - 1][1] = nums[j];
                        ans[*returnSize - 1][2] = nums[k];
                        ans[*returnSize - 1][3] = nums[l];
                        break;
                    }
                    else
                        right = mid;
                }

            }
        *returnColumnSizes = malloc((*returnSize) * sizeof(int));
        for (int i = 0; i < (*returnSize); i++)
            (*returnColumnSizes)[i] = 4;
    return ans;
}

我认为这是相当最优的解决方案，但它甚至没有超过时间限制。

Answer 1

小数组大小允许为

n*(n-1)/2

结构对（~20000）创建存储，包含所有可能对和相应索引的总和

按总和值对结构进行排序

然后，对于具有

S

索引的每个总和

i,j

，查找与

target-S

和不同于

i,j

的索引对（从左侧扫描总和，从右侧扫描相应总和）

总体复杂度为

O(n^2*log(n))

（也可以使用哈希表，但C中没有内置哈希表）