El problema Two Sum en Python
En esta lección vas a resolver el problema Two Sum encontrando dos elementos cuya suma sea un valor dado, en una sola pasada por la lista.
Introducción
El problema
Dada una lista de precios y un presupuesto, ¿qué dos artículos cuestan exactamente el presupuesto? Revisar todas las parejas funciona, pero cuesta unas n² / 2 comparaciones. Recordar lo que ya has visto permite hacerlo en una sola pasada.
Imagínalo así
Two Sum es como ir de compras con un presupuesto exacto. Con cada etiqueta de precio calculas cuánto te falta y miras tus notas: ¿ya vi algún artículo que cueste justo eso? Si es así, ya tienes la pareja. Si no, apuntas este precio y dónde lo viste, y sigues.
complement = target - value🤔 El precio que todavía faltaif complement in seen:📋 ¿Ese precio ya está en mis notas?return [seen[complement], index]🛍️ Pareja encontrada: las dos posicionesseen[value] = index✍️ Apunta este precio y su posición, y sigueEl problema Two Sum pide las posiciones de dos números de una lista que suman un objetivo. Un diccionario con los valores ya vistos lo resuelve en una sola pasada, en tiempo O(n).
Puntos clave
complement = target - valuees el valor que completaría la pareja.seenrelaciona cada valor ya visitado con su índice, así las búsquedas son rápidas.if complement in seen:encuentra la pareja entre los valores anteriores.seen[value] = indexse guarda después de la comprobación, así un valor nunca se empareja consigo mismo.- Para 9, el valor 7 encuentra a su pareja 2 en el índice 0, lo que da
[0, 1].
¿Cuándo se usa?
- Encontrar parejas con una suma o diferencia dada.
- Aprender a cambiar memoria por velocidad con una tabla hash.
- Una pregunta muy común en entrevistas y la base de 3-Sum y problemas parecidos.
Cuándo no hace falta
- Entrada ordenada con poca memoria: dos punteros desde ambos extremos no usan memoria extra.
- Necesitas todas las parejas, no solo una: reúne los resultados en lugar de devolver en la primera coincidencia.
Código de ejemplo
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Resultado de la ejecución
[0, 1]
Explicación del código
El diccionario seen guarda los valores ya recorridos con su posición. Para cada elemento, el programa calcula el complemento complement = target - value y comprueba si ya está en seen. Como buscar en un diccionario cuesta O(1), el algoritmo completo se ejecuta en O(n) con O(n) de memoria adicional.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Guardar antes de comprobar
Un valor puede emparejarse consigo mismo, como 3 + 3 = 6 con un solo 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
- Contar pares con una suma Cuenta los pares de posiciones cuyos valores suman un objetivo dado. Fácil