Two Sum: encuentra los índices de dos números que sumen target. ¿Cuál es el enfoque óptimo?

Opciones

1. Dos bucles anidados sobre el array, O(n²)
2. Ordenar primero y luego búsqueda binaria de cada valor, O(n log n)
3. Una pasada con un hash map de valor a índice, O(n) (Opción correcta)
4. Recursión que prueba cada pareja de números

Respuesta

Una pasada con un hash map de valor a índice, O(n) de tiempo, O(n) de espacio

Por qué

Para cada número x, la pareja que necesitamos es target - x. En lugar de buscarla en toda la lista (O(n) cada vez), mantenemos un dict de los números vistos y su índice.

Comprueba el dict (O(1)); si la pareja está, listo; si no, guarda x. Una pasada: O(n).

Este cambio de memoria por velocidad con un hash map es uno de los trucos más comunes en entrevistas.

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

Recuerda

¿Necesitas saber rápido si ya viste X? → hash map.

Términos clave

• Tabla hash
• Notación Big-O
• Complejidad temporal
• Complejidad espacial
• Array
• Two pointers