Jardin de Conocimiento

Python · Módulo 07 · Ej 05 — Two-sum basico

4 min read

Ejercicio 05 — Two-sum basico

Dificultad: rojo · Módulo 07 (Diccionarios y sets)

Enunciado

Two-sum basico: encuentra los dos indices cuya suma es target usando dict

Cómo se resuelve

El “two-sum” es el ejercicio que enseña por qué un diccionario convierte una búsqueda lenta en una rápida: en vez de probar todas las parejas, recordamos lo que ya vimos y preguntamos al dict en tiempo constante.

  1. visto = {} — un diccionario donde la clave es un número de la lista y el valor su índice. Es nuestra “memoria” de lo que ya hemos recorrido.
  2. for i, num in enumerate(nums) — enumerate nos da a la vez el índice i y el valor num, que necesitamos para poder devolver posiciones.
  3. complemento = target - num — para cada número calculamos qué otro número haría falta para llegar al target. Si tenemos num y buscamos que sumen target, el que falta es target - num.
  4. if complemento in visto: — aquí está la clave. Preguntar si el complemento ya apareció es una búsqueda en el diccionario, que gracias al hashing es O(1): no recorre todo lo visto, va directo. Si está, ya tenemos la pareja y devolvemos [visto[complemento], i].
  5. visto[num] = i — si el complemento aún no estaba, guardamos el número actual con su índice para que futuros números puedan encontrarlo a él como su complemento. Así una sola pasada O(n) resuelve el problema.

Trampa habitual: hacerlo con dos bucles anidados que prueban todas las parejas (O(n^2)). Funciona en listas pequeñas pero se dispara con muchas. El truco del dict es cambiar tiempo por memoria: gastamos algo de espacio guardando lo visto a cambio de que cada búsqueda sea instantánea. Ojo también con guardar el número en el dict ANTES de comprobar su complemento: si lo haces al revés, un caso como [3, 3] con target 6 podría emparejar un número consigo mismo por error.

Para practicar — cópialo y complétalo

Pega este esqueleto y completa los TODO. Es la mejor forma de aprender: inténtalo antes de mirar la solución.

# Curso de Python — Modulo 07: Diccionarios y Sets
# Ejercicio 05 — PRACTICA (rellena los TODO)
# Enunciado: Two-sum basico: encuentra los dos indices cuya suma es target usando dict
# Dificultad: rojo
# Ejecutar: python3 ej05_practica.py
 
def two_sum(nums, target):
    # TODO: crea un dict vacio llamado "visto"
    #       guardara { numero: indice } para los numeros ya procesados
    visto = None
 
    # TODO: recorre nums con enumerate() para obtener (indice i, numero num)
    for i, num in enumerate(nums):
        # TODO: calcula el complemento: target - num
        complemento = None
 
        # TODO: comprueba si el complemento ya esta en "visto"
        #       si SI: devuelve [visto[complemento], i]  (los dos indices)
        #       si NO: guarda visto[num] = i  (este numero puede ser complemento futuro)
        pass
 
    return []  # no se encontro solucion
 
 
# Casos de prueba — no modifiques esta parte
casos = [
    ([2, 7, 11, 15], 9),    # esperado: [0, 1]
    ([3, 2, 4], 6),          # esperado: [1, 2]
    ([3, 3], 6),             # esperado: [0, 1]
]
 
for nums, target in casos:
    resultado = two_sum(nums, target)
    print(f"nums={nums}, target={target} -> {resultado}")

Solución — cópiala y ejecútala

# Curso de Python — Modulo 07: Diccionarios y Sets
# Ejercicio 05 — MODELO (resuelto)
# Enunciado: Two-sum basico: encuentra los dos indices cuya suma es target usando dict
# Dificultad: rojo
# Ejecutar: python3 ej05_modelo.py
 
def two_sum(nums, target):
    """
    Para cada numero, calcula su complemento (target - num).
    Si el complemento ya esta en el dict, encontramos la pareja.
    Si no, guardamos el numero actual y su indice en el dict.
    Complejidad: O(n) tiempo, O(n) espacio.
    """
    visto = {}  # clave: numero, valor: indice donde aparecio
 
    for i, num in enumerate(nums):
        complemento = target - num
        if complemento in visto:
            return [visto[complemento], i]
        visto[num] = i
 
    return []  # no se encontro solucion
 
# Casos de prueba
casos = [
    ([2, 7, 11, 15], 9),    # esperado: [0, 1]
    ([3, 2, 4], 6),          # esperado: [1, 2]
    ([3, 3], 6),             # esperado: [0, 1]
]
 
for nums, target in casos:
    resultado = two_sum(nums, target)
    print(f"nums={nums}, target={target} -> {resultado}")

Cómo usarlo

Pega el código en un fichero y ejecútalo con tu toolchain habitual (o el botón de Ejecutar de tu editor). Antes de mirar la solución, intenta completar tú el esqueleto: es la mejor forma de aprender.

Conexiones

Graph View

Backlinks