Saltar al contenido

Two Sum

Lección 2 de 8 · 5 min

Two Sum

Paso 1 de 8

Revisar cada par es O(n²). En cambio, recorre una vez y recuerda lo que ya pasó.

La idea

Comparar cada par cuesta O(n²). En su lugar, recorre la lista una vez y hazle una sola pregunta a un hash map (tabla hash de pares clave-valor; en Python, dict) de valores vistos: ¿ya pasó el complemento, es decir, el objetivo menos este valor? La búsqueda por hash responde al instante, así que una sola pasada lo resuelve.

Ejemplo del mundo real

Una ferretería tiene un cajón de recortes de madera, y un cliente necesita exactamente 240 cm con dos piezas. El empleado mide cada recorte una sola vez y anota las longitudes en una libreta; después de cada medida, busca en la libreta el resto que falta en lugar de volver a revolver el cajón.

El código

Te toca

Completa el espacio en blanco.

def two_sum(nums, target):
  seen = {}
  for i, x in enumerate(nums):
      if ___ in seen:
          return (seen[target - x], i)
      seen[x] = i

print(two_sum([90, 40, 200, 40], 240))   # want (1, 2)

Mini quiz

1 / 3

¿Cuál es la complejidad temporal de Two Sum con hash map?