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