Two Sum
Recibes un array de enteros nums y un entero target. Exactamente dos elementos de nums, en dos posiciones diferentes, suman target. Devuelve los índices de esos dos elementos, primero el índice menor.
Función
- numsinteger-array
- el arreglo de enteros que se debe buscar
- targetinteger
- la suma que deben alcanzar las dos entradas
- Devuelveinteger-array
- los dos índices, primero el menor
Restricciones
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- Exactamente un par de posiciones diferentes suma
target.
Ejemplos
- Entrada
- nums = [3, 8, 12, 5]target = 17
- Salida
- [2, 3]
- Explicación
- 12 está en el índice 2 y 5 en el índice 3, y 12 + 5 = 17. Ningún otro par llega a 17.
- Entrada
- nums = [6, 1, 4, 10]target = 7
- Salida
- [0, 1]
- Explicación
- 6 en el índice 0 y 1 en el índice 1 suman 7: el par puede ser las dos primeras entradas.
- Entrada
- nums = [2, -6, 9, 4, 13]target = 3
- Salida
- [1, 2]
- Explicación
- -6 en el índice 1 y 9 en el índice 2 suman 3. Los números negativos se emparejan igual que los positivos.
Para ir más allá
Si nums ya estuviera ordenado, ¿podrías encontrar el par en O(n) de tiempo usando solo O(1) de memoria adicional?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Probar cada par con dos bucles anidados es correcto, pero con 10,000 números eso supone unos 50 millones de comprobaciones. ¿Puedes encontrar la pareja de cada número sin volver a recorrer la lista?
Cuando te encuentras en un valor
x, ya sabes qué valor completaría el par: el objetivo menosx. La única pregunta es si ya has pasado por ese valor y en qué índice.Recorre la lista una vez y mantén un mapa hash de cada valor por el que hayas pasado y su índice. En cada posición, busca primero el complemento que falta; si está en el mapa, ya tienes ambos índices. De lo contrario, almacena el valor actual y continúa. Buscar antes de almacenar es lo que evita que un número se empareje consigo mismo.
Solución
Comprobar cada par funciona, pero el trabajo crece con el cuadrado de la longitud. Invierte la pregunta: al situarte sobre un número x, ya sabes que su complemento debe ser target - x. Un mapa hash te indica en tiempo constante si ya has pasado por ese valor, así que basta con una sola pasada.
Comprueba cada par
Correcto, pero no termina con las pruebas más grandes
Intuición
Fija un primer índice i y prueba cada índice j a su derecha hasta que nums[i] + nums[j] sea igual a target. Empezar j en i + 1 evita que una posición se empareje consigo misma, prueba cada par una sola vez y coloca primero el índice menor. El par que buscas es uno de los pares que pruebas, así que lo encuentras.
n números forman aproximadamente n²/2 pares: n = 10^4 significa cerca de 5 × 10^7 sumas.
Algoritmo
- Recorre con un bucle
itodos los índices denums. - Para cada
i, recorre con un buclejdesdei + 1hasta el último índice. - Si
nums[i] + nums[j]es igual atarget, devuelve[i, j]. - Si ambos bucles terminan, devuelve un array vacío. El problema garantiza que esto nunca ocurre.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []Una pasada con un mapa hash
Intuición
Para un nums[i] fijo, el bucle interno de la fuerza bruta busca un valor que conoces de antemano: target - nums[i]. Esa búsqueda es en realidad una consulta, y un mapa hash que asocia valores con índices permite realizar consultas en tiempo constante en promedio.
Primero busca y luego almacena. Así, un número solo puede emparejarse con otro que aparezca antes que él, nunca consigo mismo y, como su compañero siempre está antes, su índice aparece primero. Cada número se visita una vez con operaciones del mapa en tiempo constante, así que la búsqueda es O(n); el precio es un mapa de hasta n entradas.
Algoritmo
- Crea un mapa vacío de valores a índices.
- Para cada índice
i, calculaneed, el valor que completa el par:targetmenosnums[i]. - Si
needestá en el mapa, devuelve su índice almacenado seguido dei. - De lo contrario, almacena
nums[i]con el índiceiy continúa.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
Errores comunes y casos límite
- Almacenar un número antes de buscar su complemento. Con
[4, 2, 6]ytarget = 8, el 4 se encuentra consigo mismo y devuelves[0, 0]. - Devolver los índices en el orden incorrecto. Si buscas antes de almacenar, el índice del mapa es el menor y va primero.
- Ordenar el array para usar dos punteros y luego devolver las posiciones de la copia ordenada. Mantén el índice original de cada valor junto a él.
- Suponer que los valores son positivos o distintos.
[0, 7, -3, 0]contarget = 0empareja los dos ceros:[0, 3]. - En Lua y R, devolver los índices basados en 1. Resta 1 a cada uno.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Two Sum?
La solución con mapa hash se ejecuta en tiempo O(n), porque visita cada número una vez y cada búsqueda o inserción toma un tiempo constante en promedio. Usa O(n) de espacio adicional para el mapa. Comprobar cada par toma O(n²) de tiempo y O(1) de espacio.
¿Se puede resolver Two Sum sin espacio adicional?
No en tiempo lineal en un arreglo sin ordenar. Con espacio adicional O(1), vuelves a comprobar cada par, lo que es O(n²). El mapa hash intercambia memoria O(n) por tiempo lineal.
¿Cómo maneja Two Sum los números duplicados?
Los duplicados funcionan cuando buscas el complemento antes de guardar el número actual. En [7, 3, 7] con target = 14, el primer 7 se guarda en el índice 0 y el segundo 7 lo encuentra, lo que da [0, 2]. Un 7 aislado nunca forma pareja consigo mismo: aún no está en el mapa cuando lo buscas.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def twoSum(nums, target):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
nums = [3, 8, 12, 5] target = 17
Salida Esperada
[2, 3]