Algoritmos en Python

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.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

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.

De comprar con presupuesto al código
complement = target - value🤔 El precio que todavía falta
if complement in seen:📋 ¿Ese precio ya está en mis notas?
return [seen[complement], index]🛍️ Pareja encontrada: las dos posiciones
seen[value] = index✍️ Apunta este precio y su posición, y sigue
Busca el precio que falta en vez de probar todas las parejas.
En una frase

El 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

  1. complement = target - value es el valor que completaría la pareja.
  2. seen relaciona cada valor ya visitado con su índice, así las búsquedas son rápidas.
  3. if complement in seen: encuentra la pareja entre los valores anteriores.
  4. seen[value] = index se guarda después de la comprobación, así un valor nunca se empareja consigo mismo.
  5. 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

Ejecutar código →
main.py
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))
Obtén un botón Run para este ejemplo

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.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Errores comunes

Guardar antes de comprobar

Un valor puede emparejarse consigo mismo, como 3 + 3 = 6 con un solo 3.

Problema
seen[value] = index
if target - value in seen:
Solución
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.

Todos los retos