Encuentra cuatro, cuya suma sea igual al objetivo.

Problema:
dada una matriz de n números enteros, devuelva una matriz de todos los cuatrillizos únicos [nums[a], nums[b], nums[c], nums[d]] tal que:

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

Puede devolver la respuesta en cualquier orden.

Ejemplo 1:

Entrada: números = [1,0,-1,0,-2,2], objetivo = 0 Salida: [[-2,-1,1,2],[-2,0,0,2],[ -1,0,0,1]]

Ejemplo 2:

Entrada: números = [2,2,2,2,2], objetivo = 8 Salida: [[2,2,2,2]]
Restricciones:

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

Algoritmo:

1. Primero ordenamos una matriz;
2. Elija tres números diferentes;
3. Encuentra el cuarto número, que tiene que ser igual atarget - num1 - num2 - num3

.

código 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;
}

Pensé que esta es una solución bastante óptima, pero ni siquiera pasa el límite de tiempo.

Feb 15 '24 23:02 iskander