3Sum

+10

Se te proporciona una lista de números enteros nums. Encuentra cada triplete [a, b, c] de valores tomados de tres posiciones distintas de nums que cumpla a + b + c = 0. Escribe cada triplete en orden no decreciente (a ≤ b ≤ c) y enumera cada triplete distinto una sola vez, incluso cuando varias elecciones de posiciones lo produzcan. Devuelve los tripletes ordenados por su primer valor y, después, por el segundo.

Función

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: la lista de números enteros, con al menos tres elementos
Devuelveinteger-2d-array: cada tripleta distinta que suma 0, cada una en orden no decreciente, la lista ordenada

Restricciones

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Al menos una terna suma 0.
Dos ternas son iguales cuando contienen los mismos tres valores.

Ejemplos

Entrada: nums = [-2, 0, 1, 1, -1, 2]
Salida: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explicación: -2 + 0 + 2, -2 + 1 + 1 y -1 + 0 + 1 dan como resultado 0. [-2, 1, 1] puede usar el valor 1 dos veces porque 1 ocupa dos posiciones, mientras que [-1, 0, 1] puede construirse con cualquiera de los dos valores 1, pero aparece una sola vez.

Entrada: nums = [0, 0, 0, 0]
Salida: [[0, 0, 0]]
Explicación: Cualesquiera tres de los cuatro ceros suman 0. Hay cuatro opciones de posiciones, pero todas dan la misma tripleta, así que la respuesta contiene [0, 0, 0] una sola vez.

+15 pruebas ocultas al enviar

Para ir más allá

El mismo patrón resuelve 4Sum: fija dos valores y usa dos punteros con el resto. ¿Puedes escribirlo en O(n³) y aplicar correctamente las reglas para evitar duplicados en cada nivel?

Pistas

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

0 de 3 abiertas

Solución

Dos cosas hacen que 3Sum sea más difícil de lo que parece. Comprobar cada triplete cuesta O(n³), y la respuesta debe incluir cada triplete una sola vez, incluso cuando se repiten los valores. Ordenar resuelve ambos problemas: los valores iguales quedan uno al lado del otro, así que puedes omitir las repeticiones comparando los elementos vecinos, y, una vez fijado el valor más pequeño, los otros dos forman un problema de suma de pares en una lista ordenada que se resuelve con dos punteros en un solo recorrido.

Prueba cada tripleta

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

Intuición

Ordena primero la lista. Luego, cualesquiera tres posiciones i < j < k dan valores que ya están ordenados, nums[i] ≤ nums[j] ≤ nums[k], así que una tripleta queda escrita correctamente en cuanto la encuentras. Tres bucles anidados recorren todas las combinaciones de posiciones, por lo que no se puede pasar por alto ninguna tripleta.

A continuación, los valores repetidos. El primer ejemplo, una vez ordenado, es [-2, -1, 0, 1, 1, 2], y [-1, 0, 1] puede tomar su 1 del índice 3 o del índice 4. Por tanto, cada bucle omite una posición cuyo valor es igual al que ese mismo bucle probó antes. Luego, cada bucle prueba cada valor distinto una sola vez, y cada tripleta distinta aparece una sola vez, ya ordenada. El salto solo compara con la posición anterior dentro del mismo bucle, así que [-2, 1, 1] sigue usando los dos unos.

El problema es el costo. Hay aproximadamente n³/6 ternas: para 3000 números, son 4.5 × 10^9 sumas, muy por encima de cualquier límite de tiempo.

Algoritmo

Ordena nums.
Recorre las posiciones con i y omite i cuando nums[i] sea igual a nums[i-1].
Dentro de ese bucle, recorre j desde i+1 y omite j cuando j > i+1 y nums[j] sea igual a nums[j-1].
Dentro de ese bucle, recorre k desde j+1 con la misma regla para omitir, y registra [nums[i], nums[j], nums[k]] cuando los tres sumen 0.
Devuelve las tripletas en el orden en que las encontraste. Ya están ordenadas.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            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):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fija un valor y encuentra el par con un conjunto hash

Intuición

Una vez fijado el primer valor nums[i], necesitas dos valores posteriores que sumen -nums[i]. Eso es Two Sum. Recorre j hacia la derecha de i y mantén un conjunto de los valores por los que has pasado. En cada j, el valor que falta es need = -nums[i] - nums[j]. Si need está en el conjunto, [nums[i], need, nums[j]] suma 0. Consultar un conjunto cuesta O(1) en promedio, así que para un i cuesta O(n) y la búsqueda completa cuesta O(n²).

La ordenación sigue encargándose de llevar el control. Omite un i cuyo valor sea igual al anterior. Después de encontrar una coincidencia, avanza j más allá de cada copia de nums[j]: con el primer y el tercer valor fijados, el del medio también queda fijado, así que otra copia solo podría repetir la misma tripleta. Como need proviene de una posición anterior de la lista ordenada, need ≤ nums[j] y la tripleta queda ordenada. También puedes detenerte en cuanto nums[i] > 0: los dos valores que vienen después son al menos igual de grandes, así que la suma no puede llegar a 0.

Un detalle: a medida que j avanza hacia la derecha, nums[j] aumenta y need disminuye, así que las tripletas de un mismo i aparecen con el valor del medio en orden descendente. En [-2, -1, 0, 1, 1, 2], con i = 0, encuentras [-2, 1, 1] en el segundo 1 y luego [-2, 0, 2] en el 2. Invierte cada grupo antes de añadirlo a la respuesta. Las versiones en C y R marcan los valores vistos en un arreglo indexado por valor en lugar de usar un conjunto hash, lo cual funciona porque todos los valores están dentro del rango ±10^5.

Algoritmo

Ordena nums.
Para cada i, detente cuando nums[i] > 0 y omite i cuando nums[i] sea igual a nums[i-1].
Empieza con un conjunto vacío. Para cada j a partir de i+1, calcula need = -nums[i] - nums[j]. Si need está en el conjunto, registra [nums[i], need, nums[j]] y avanza j más allá de las copias de nums[j].
Añade nums[j] al conjunto y continúa con el siguiente j.
Invierte las ternas encontradas para este i y añádelas a la respuesta.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Ordena y usa dos punteros

Intuición

El orden ordenado puede reemplazar al conjunto. Fija nums[i], coloca lo en i+1 y hi en el último índice, y observa nums[i] + nums[lo] + nums[hi]. Si el resultado es menor que 0, necesitas un valor mayor, así que lo avanza hacia la derecha. Si es mayor que 0, necesitas uno menor, así que hi retrocede hacia la izquierda. Si es exactamente 0, registra la terna y mueve ambos.

No se pierde ninguna terna. Cuando la suma es menor que 0, nums[lo] se queda corto incluso con el mayor valor restante, nums[hi], así que no puede formar pareja con ningún valor que siga dentro del rango y descartarlo no hace perder nada. Si es mayor que 0, ocurre lo contrario: nums[hi] es demasiado grande incluso con el menor valor restante. En cada paso se descarta un valor de forma definitiva, así que un i cuesta como máximo n pasos y la búsqueda completa O(n²), sin usar memoria adicional aparte de la necesaria para ordenar y almacenar la salida.

Tomemos la lista ordenada [-2, -1, 0, 1, 1, 2]. Con i = 0 (valor -2), lo empieza en -1 y hi en 2: la suma es -1, así que lo avanza hasta 0. Ahora -2 + 0 + 2 = 0, así que registras [-2, 0, 2] y ambos punteros quedan en los dos 1, que dan [-2, 1, 1]. Con i = 1 (valor -1), 0 y 2 dan 1, así que hi retrocede hasta el segundo 1, y -1 + 0 + 1 = 0 registra [-1, 0, 1]. El valor 0 en i = 2 no encuentra nada, y en i = 3 el valor es positivo, así que la búsqueda se detiene.

Los valores repetidos requieren dos reglas. Omite un i cuyo valor sea igual al anterior. Después de encontrar una coincidencia, mueve lo más allá de las copias del valor que utilizó. hi no necesita una regla propia: con lo en un valor mayor, una copia del antiguo nums[hi] ahora da una suma mayor que 0 y se descarta por sí sola. Como i recorre los valores distintos en orden creciente y lo solo avanza hacia la derecha, las ternas salen ordenadas.

Algoritmo

Ordena nums.
Para cada i, detente cuando nums[i] > 0 y omite i cuando nums[i] sea igual a nums[i-1].
Establece lo = i+1 y hi = n-1. Mientras lo < hi, suma nums[i], nums[lo] y nums[hi].
Si la suma es menor que 0, mueve lo hacia la derecha. Si es mayor que 0, mueve hi hacia la izquierda.
Si es 0, registra la terna, mueve ambos punteros y después mueve lo más allá de las copias del valor que usó.
Devuelve las ternas. Ya están ordenadas.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a valores repetidos, así que prueba con entradas que los contengan.

Omitir i cuando nums[i] es igual a nums[i+1] conserva la última copia de cada valor como primer elemento, y las copias anteriores desaparecen. En [-1, -1, 2], eso elimina [-1, -1, 2]. Compara con la posición anterior, nums[i-1].
Detenerse cuando nums[i] ≥ 0 en lugar de cuando nums[i] > 0 no detecta [0, 0, 0].
Eliminar los repetidos al final en lugar de omitirlos. Con 3000 ceros, el bucle de dos punteros registra millones de copias de [0, 0, 0] antes de cualquier limpieza y, en varios lenguajes, un conjunto de listas compara las listas por identidad, así que las copias sobreviven de todos modos.
Usar una posición dos veces. Una versión con un conjunto hash que llena el conjunto con toda la lista de antemano convierte [-2, 1, 3] en [-2, 1, 1] al usar el único 1 dos veces. Busca valores únicamente en posiciones por las que ya hayas pasado.
Devolver las ternas desordenadas. La comparación es exacta, así que la versión con conjunto hash debe invertir cada grupo, y una solución que recopila ternas en un conjunto debe ordenarlas al final.

Preguntas frecuentes4

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

La solución de ordenar y usar dos punteros se ejecuta en tiempo O(n²). Ordenar cuesta O(n log n), y cada una de las n elecciones del primer valor requiere un recorrido de O(n). Necesita O(1) espacio adicional, aparte del ordenamiento y la salida. Comprobar cada tripleta requiere O(n³) en cambio.

¿Cómo evita 3Sum las tripletas duplicadas?

Ordena la lista, así que los valores iguales quedan uno al lado del otro. Después omite un valor si es igual al anterior y, después de cada coincidencia, mueve el puntero izquierdo más allá de las copias del valor que utilizó. Cada triplete se encuentra una sola vez, a partir de las primeras copias de sus valores, así que no se necesita ningún conjunto de resultados.

¿Debería usar dos punteros o un conjunto hash para 3Sum?

Ambos se ejecutan en tiempo O(n²). Los dos punteros no necesitan memoria adicional, y el orden ordenado te proporciona las tripletas ya ordenadas. Un conjunto hash cuesta O(n) de memoria y requiere cuidado para mantener distintas las posiciones y ordenar la salida. La idea del conjunto hash es importante cuando no puedes ordenar, como en Two Sum, donde devuelves los índices originales.

¿Se puede resolver 3Sum más rápido que en O(n²)?

No por mucho. Los algoritmos más conocidos superan a n² solo por unos pocos factores logarítmicos, y muchos resultados de dificultad en geometría computacional suponen que ningún algoritmo alcanza una potencia de n inferior a 2. Esos algoritmos más rápidos son resultados de investigación, así que O(n²) es la respuesta que se espera en las entrevistas.

Python

def threeSum(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado

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

3Sum

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada tripleta

Fija un valor y encuentra el par con un conjunto hash

Ordena y usa dos punteros

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares