Two-sum con un mapa hash en Python
El clásico problema de entrevista en tiempo lineal.
def suma_dos(numeros, objetivo):
vistos = {}
for i, n in enumerate(numeros):
falta = objetivo - n
if falta in vistos:
return (vistos[falta], i)
vistos[n] = i
return None
par = suma_dos([2, 7, 11, 15], 9)
fallo = suma_dos([1, 2, 3], 100)Cómo funciona
- Un dict recuerda el índice de cada valor mientras escanea.
- Para cada número busca el complemento que necesita.
- Un acierto devuelve el par; si no, registra y sigue.
Palabras clave y builtins usados aquí
defenumerateforifreturn
El intento, en números
- Líneas
- 12
- Caracteres a escribir
- 238
- Tokens
- 79
- Ritmo de tres estrellas
- 100 tpm
Al ritmo de tres estrellas de 100 tokens por minuto, este intento toma unos 47 segundos.
Paso 1 de 5 en Algoritmos; paso 51 de 72 en Fundamentos del lenguaje.