4Sum

Q: ¿Cuál es la complejidad temporal de 4Sum?

O(n³). Los dos bucles seleccionan aproximadamente n²/2 pares (i, j) , y cada uno realiza un recorrido con dos punteros de como máximo n pasos; la ordenación O(n log n) es insignificante en comparación.

Q: ¿Cómo generalizas 4Sum a kSum?

Escribe kSum(nums, target, k) sobre una lista ordenada. Para k = 2, ejecuta el recorrido con dos punteros. Para un k mayor, itera sobre el primer valor, omite los repetidos y se llama a sí misma con k-1 y target - nums[i] sobre los valores a la derecha. Cada nivel añade un factor de n, así que kSum cuesta O(n^(k-1)).

Q: ¿Se puede resolver 4Sum en O(n²)?

Puedes agrupar las n²/2 sumas de pares en un mapa hash y emparejar cada par con los pares cuya suma sea target menos la suya. Esto es rápido cuando pocos pares comparten una suma, pero una suma puede contener O(n²) pares, así que, en el peor de los casos, no es mejor que O(n³).

MedioDos punteros Ordenación

+10

Recibes una lista de enteros nums y un entero target. Devuelve cada cuádrupla [a, b, c, d] cuyos cuatro valores se encuentran en cuatro posiciones diferentes de nums y suman target. Escribe cada cuádrupla con sus valores en orden no decreciente. Si se pueden elegir los mismos cuatro valores en posiciones diferentes, la cuádrupla aparece una sola vez. Ordena la respuesta primero por el primer valor, después por el segundo y luego por el tercero. Si ninguna cuádrupla cumple las condiciones, devuelve una lista vacía.

Función

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: los números entre los que elegir, al menos uno
targetinteger: la suma que debe alcanzar cada cuarteto
Devuelveinteger-2d-array: los cuartetos distintos cuya suma sea el objetivo, cada uno ordenado y también la lista ordenada; una lista vacía si no hay ninguno

Restricciones

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
La suma de cuatro valores cualesquiera se encuentra entre -4 × 10⁸ y 4 × 10⁸, así que cabe en un entero de 32 bits.
Los cuádruples que contienen los mismos cuatro valores cuentan como uno.

Ejemplos

Entrada: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Salida: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Explicación: Cada uno de los cuatro cuádruples suma 1, por ejemplo -3 + (-1) + 2 + 3. Los dos que empiezan por -3 van primero, ordenados por su segundo valor: -1 antes que 0.

Entrada: nums = [4, 4, 4, 4, 4, 4]target = 16
Salida: [[4, 4, 4, 4]]
Explicación: Las 15 elecciones de cuatro posiciones de entre seis dan cuatro 4 que suman 16, así que [4, 4, 4, 4] aparece una vez.

Entrada: nums = [1, 5, 2, 9]target = 3
Salida: []
Explicación: La única opción son los cuatro números, y 1 + 5 + 2 + 9 = 17, no 3, así que la respuesta es una lista vacía.

Para ir más allá

Cuenta los conjuntos de cuatro posiciones cuyos valores suman target, en lugar de los cuádruples distintos. El segundo ejemplo tiene 15. ¿Puedes hacerlo en O(n²)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Comprobar cada conjunto de cuatro posiciones cuesta O(n⁴), y los valores repetidos generan el mismo cuádruple muchas veces. Aplica la reducción de 3Sum un nivel más profundo: ordena, fija los dos primeros valores con dos bucles, encuentra el último par con dos punteros y omite los valores repetidos en cada nivel.

Prueba cada conjunto de cuatro

Correcto, pero no termina con las pruebas más grandes

Intuición

Ordena primero, para que las posiciones i < j < k < l contengan valores en orden no decreciente y cada cuádrupla salga escrita de la forma correcta. Cuatro bucles anidados recorren todas las combinaciones de cuatro posiciones. Para evitar repeticiones, un bucle avanza cuando su siguiente posición contiene el valor que probó un paso antes. Con seis 4, cada bucle prueba solo su primera posición, así que [4, 4, 4, 4] aparece una vez en lugar de 15 veces.

Para 200 números hay 64,684,950 conjuntos de cuatro, y la cantidad crece aproximadamente 16 veces cuando n se duplica.

Algoritmo

Ordena nums.
Anida cuatro bucles sobre i < j < k < l, cada uno empezando una posición después del bucle que lo contiene.
En cada bucle, omite una posición que no sea la primera del bucle y que tenga el mismo valor que la posición anterior.
Registra [nums[i], nums[j], nums[k], nums[l]] cuando los cuatro sumen target. Los bucles los producen en orden ordenado.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Ordenar, dos bucles, dos punteros

Intuición

Fija nums[i] y nums[j], y lo que queda es un problema de pares: encuentra dos valores a la derecha de j que sumen target - nums[i] - nums[j]. En una lista ordenada, un solo recorrido lo resuelve. Empieza con lo en j+1 y hi en el último índice. Si la suma es menor que target, mueve lo a la derecha; si es mayor, mueve hi a la izquierda.

Cada movimiento descarta un valor que no forma parte de ninguna respuesta. Si la suma es demasiado pequeña, ni siquiera el mayor valor restante, nums[hi], es suficiente para nums[lo], así que puedes descartar nums[lo]. Si la suma es demasiado grande, descarta nums[hi] por la razón inversa. Un par (i, j) requiere como máximo n movimientos, así que los n²/2 pares cuestan O(n³).

En el primer ejemplo, con i en -3 y j en -1, lo se mueve desde 0, pasa por 1 y llega a 2, donde -3 + (-1) + 2 + 3 = 1.

Algoritmo

Ordena nums.
Para cada i, omítelo cuando i > 0 y nums[i] sea igual a nums[i-1].
Para cada j después de i, omítelo cuando j > i+1 y nums[j] sea igual a nums[j-1].
Establece lo = j+1 y hi = n-1. Mientras lo < hi, compara la suma de los cuatro valores con target: si es menor, mueve lo hacia la derecha; si es mayor, mueve hi hacia la izquierda.
Si hay una coincidencia, registra la cuaterna, mueve ambos punteros y luego avanza lo mientras contenga el valor que usó.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Errores comunes y casos límite

Omitir j siempre que nums[j] sea igual a nums[j-1]. En j = i+1, eso se compara con el valor que usa i, por lo que [2, 2, 2, 2, 2] con el objetivo 8 pierde [2, 2, 2, 2].
Copiar la salida anticipada de 3Sum nums[i] > target. Con [-5, -4, -3, -2, -1] y el objetivo -10, el bucle se detiene en -5 y no encuentra [-4, -3, -2, -1].
Listas con menos de cuatro elementos. Con uno o dos números, n-3 es negativo: 0..<(n - 3) provoca una trampa en Swift, y n - 3 en un usize de Rust produce un desbordamiento por defecto. Devuelve primero una lista vacía.
Recopilar las cuádruplas en un conjunto hash y devolverlas sin ordenar.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de 4Sum?

O(n³). Los dos bucles seleccionan aproximadamente n²/2 pares (i, j), y cada uno realiza un recorrido con dos punteros de como máximo n pasos; la ordenación O(n log n) es insignificante en comparación.

¿Cómo generalizas 4Sum a kSum?

Escribe kSum(nums, target, k) sobre una lista ordenada. Para k = 2, ejecuta el recorrido con dos punteros. Para un k mayor, itera sobre el primer valor, omite los repetidos y se llama a sí misma con k-1 y target - nums[i] sobre los valores a la derecha. Cada nivel añade un factor de n, así que kSum cuesta O(n^(k-1)).

¿Se puede resolver 4Sum en O(n²)?

Puedes agrupar las n²/2 sumas de pares en un mapa hash y emparejar cada par con los pares cuya suma sea target menos la suya. Esto es rápido cuando pocos pares comparten una suma, pero una suma puede contener O(n²) pares, así que, en el peor de los casos, no es mejor que O(n³).

def fourSum(nums, target):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

nums = [3, -1, 0, 2, -2, 1, -3]
target = 1

Salida Esperada

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]