Lumænaut_

Bienvenido, valiente programador. Si estás comenzando tu viaje en LeetCode, Two Sum es casi con certeza el primer problema que encontrarás. Es como el “hola mundo” de las entrevistas algorítmicas — sencillo en la superficie, pero lleno de lecciones que resonarán a lo largo de toda tu carrera como programador. En este post, lo desglosaremos juntos. Sin jerga intimidante, sin saltarnos pasos. Comenzaremos con la solución más ingenua, nos reiremos de sus defectos, y luego la transformaremos en algo hermoso y rápido. Toma una taza de café (o té, no juzgamos), y comencemos.

El problema — Two Sum (LeetCode 1)

Antes de sumergirnos en las soluciones, leamos el enunciado original del problema:

Dado un arreglo de enteros nums y un entero target, devuelve los índices de los dos números que suman target.

Puedes asumir que cada entrada tendrá exactamente una solución, y no puedes usar el mismo elemento dos veces.

Puedes devolver la respuesta en cualquier orden.

Reescribiendo en español sencillo

Imagina que tienes una lista de números (como [2, 7, 11, 15]) y un número objetivo (como 9). Necesitas encontrar dos números dentro de la lista que sumen el objetivo. Luego devuelves sus posiciones (índices) — no los números en sí. Además, cada elemento solo puede usarse una vez. Y el rompecabezas garantiza que hay exactamente un par válido escondido ahí. Eso significa que nunca te quedarás atascado preguntándote “¿qué combinación es la correcta?” — solo hay una respuesta correcta.

Ejemplos del problema

• Ejemplo 1: nums = [2,7,11,15], target = 9 → Salida: [0,1] porque 2 + 7 = 9.
• Ejemplo 2: nums = [3,2,4], target = 6 → Salida: [1,2] porque 2 + 4 = 6 (índices 1 y 2).
• Ejemplo 3: nums = [3,3], target = 6 → Salida: [0,1]. Los dos 3 están en posiciones diferentes.

¿Sencillo, verdad? Sin embargo, el verdadero desafío es qué tan rápido podemos encontrarlos cuando el arreglo se vuelve enorme — hasta 10,000 números. Ahí es donde comienza la diversión.

El enfoque ingenuo: fuerza bruta (“revisar cada pareja”)

Seamos honestos: cuando vemos un problema como este por primera vez, nuestro cerebro instintivamente piensa: “Tomaré el primer número, y luego intentaré sumarlo con cada otro número después de él. Si coincide con el objetivo, ¡listo!” Ese es el enfoque de fuerza bruta. Es simple, es honesto, y funciona. Pero también es el más lento.

Flujo de fuerza bruta:
Para i desde 0 hasta n-1:
  Para j desde i+1 hasta n-1:
    Si nums[i] + nums[j] == target → devolver [i, j]

Código (Python).

def twoSum_fuerza_bruta(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # nunca se alcanza porque existe una solución

Complejidad — las malas noticias

Si el arreglo tiene n elementos, el bucle externo se ejecuta n veces, y el bucle interno se ejecuta alrededor de n/2 veces en promedio. Eso nos da aproximadamente n * (n-1)/2 operaciones, que en notación Big O es O(n²). Para n = 10,000, ¡eso es alrededor de 50 millones de comparaciones! Tu computadora puede manejarlo, pero en una entrevista te preguntarán: ¿Puedes hacerlo mejor?

Pero el enfoque de fuerza bruta sigue siendo importante — es la base. Siempre comenzamos con la solución funcional más simple, y luego optimizamos.

El momento “¡Ajá!”: usar una memoria (hash map)

Aquí está la idea clave: en lugar de revisar cada pareja, podemos recordar qué números hemos visto y hacer una pregunta simple: “¿Necesito un número específico para completar el objetivo?”

Desglosémoslo: Para cada número x, el complemento es objetivo - x. Si ya hemos visto ese complemento en algún lugar del arreglo, ¡encontramos nuestro par! Solo necesitamos una forma de almacenar los números que hemos pasado y consultarlos rápidamente. Ahí es donde entra un hash map (también llamado tabla hash o diccionario) — una estructura de datos que permite almacenar pares clave-valor y verificar si una clave existe en O(1) en promedio. Súper rápido.

El algoritmo inteligente (una sola pasada)

Recorremos el arreglo una sola vez. Para cada elemento nums[i]:

1. Calculamos complemento = objetivo - nums[i].
2. Verificamos si el complemento ya existe en nuestro hash map. Si es así → devolvemos [map[complemento], i].
3. De lo contrario, almacenamos el número actual y su índice en el mapa: map[nums[i]] = i.

Flujo del hash map de una pasada:
mapa = {}
para i en 0..n-1:
  complemento = objetivo - nums[i]
  si complemento está en mapa: devolver [mapa[complemento], i]
  si no: mapa[nums[i]] = i
# listo

Implementación en código.

def twoSum_hashmap(nums, objetivo):
    visto = {}  # clave = número, valor = índice
    for i, num in enumerate(nums):
        complemento = objetivo - num
        if complemento in visto:
            return [visto[complemento], i]
        visto[num] = i
    return []

Recorramos el ejemplo nums = [3,2,4], objetivo = 6:

• i=0, num=3, complemento=3. visto está vacío → almacenamos {3:0}
• i=1, num=2, complemento=4. visto tiene {3:0}, 4 no está → almacenamos {3:0, 2:1}
• i=2, num=4, complemento=2. ¿visto tiene 2? ¡Sí! → devolvemos [visto[2]=1, 2] → [1,2]

Hermoso, ¿verdad? Solo recorremos el arreglo una vez.

Análisis de complejidad: por qué es un cambio radical

Complejidad temporal: O(n) — recorremos el arreglo una vez, y cada operación de hash map (inserción y búsqueda) es O(1) en promedio.
Complejidad espacial: O(n) — en el peor caso almacenamos casi todos los elementos en el hash map antes de encontrar el par.

Para n = 10,000, la fuerza bruta realiza hasta 50 millones de operaciones; la solución con hash map hace alrededor de 10,000. Esa es la diferencia entre esperar 2 segundos y 0.001 segundos.

La sección de matemáticas — entendiendo la ecuación central

Formalicemos el problema con matemáticas. Se nos da:

Reformulación del problema. Encontrar índices i y j, i ≠ j, tales que
nums[i] + nums[j] = objetivo
Equivalente a: nums[i] = objetivo - nums[j]

Si lo pensamos como una ecuación: para cada índice j, queremos encontrar un índice anterior i que cumpla nums[i] = objetivo - nums[j]. Esto es como resolver un sumando faltante. El método ingenuo revisa todos los pares; el método del hash map precalcula el conjunto de números anteriores, convirtiendo el problema en una búsqueda de tiempo constante.

Otro punto de vista matemático: considera la función f(x) = objetivo - x. Para cada número en el arreglo, su complemento está definido. Dos números forman un par válido si uno es la imagen del otro bajo f. Eso es todo lo que estamos haciendo — buscar pares de complementos en una sola pasada.

También podemos visualizarlo como: dibuja una recta numérica. Para cada x, el compañero deseado es objetivo - x. A medida que escaneamos, dejamos “migas de pan” en un hash map. En el momento en que pisamos una migaja dejada por un número anterior, tenemos nuestra solución. Es como una búsqueda del tesoro con memoria perfecta.

Seguimiento: ¿podemos hacer mejor que O(n²)?

El seguimiento del problema pregunta: “¿Puedes encontrar un algoritmo con complejidad temporal menor que O(n²)?” Y sí — ¡acabamos de hacerlo! O(n) con un hash map es dramáticamente más rápido. ¿Podríamos hacer O(n log n)? Posiblemente con ordenamiento y técnica de dos punteros, pero eso perdería los índices originales a menos que los almacenemos. El enfoque con hash map sigue siendo el más elegante para este problema específico.

Si sientes curiosidad por el método de ordenamiento: podrías ordenar el arreglo (con los índices adjuntos) y luego usar dos punteros (izquierdo y derecho) para encontrar el par. Eso es O(n log n), pero se usa a menudo cuando necesitas evitar espacio extra. Sin embargo, para Two Sum, el método con hash map es el favorito en entrevistas.

Un poco de historia: ¿de dónde viene este problema?

El problema Two Sum se hizo famoso principalmente porque fue uno de los primeros problemas en LeetCode (lanzado en 2015). Pero la idea de encontrar dos números que sumen un objetivo se remonta a décadas atrás. Es esencialmente un caso especial del problema de suma de subconjuntos de la teoría de la computación. Empresas como Google, Facebook y Amazon lo adoran porque pone a prueba tanto la habilidad básica de codificación como la transición del pensamiento ingenuo al óptimo — una habilidad fundamental en ingeniería de software.

También hay una línea directa con el uso de tablas hash, que revolucionó la forma en que manejamos las búsquedas en programación. La idea de usar un hash map para recordar valores pasados es un patrón de diseño común en entrevistas de algoritmos (lo verás nuevamente en problemas como “Subarray Sum Equals K” o “Contains Duplicate”).

Probando nuestra solución con casos límite

Revisemos algunos escenarios complicados que podrían romper un enfoque ingenuo:

• Duplicados: nums = [1, 1, 2], target = 2 → Salida: [0,1] porque 1+1=2. Nuestro hash map funciona: cuando i=1, complemento=1, visto ya tiene 1 desde el índice 0 → devuelve [0,1].
• Números negativos: nums = [-1, -2, -3, -4], target = -6 → Salida: [1,3] porque -2 + (-4) = -6. La lógica del complemento sigue funcionando.
• Números grandes: Hasta 10⁹, pero nuestra aritmética de enteros funciona bien.

Un error común para principiantes: usar el mismo elemento dos veces. Por ejemplo, si nums = [3, 2, 4], target = 6, el complemento para 3 es 3, pero no podemos usar el mismo 3 otra vez. Es por eso que almacenamos los números después de verificar el complemento, no antes. El algoritmo asegura que solo emparejamos el elemento actual con los vistos previamente.

Diagrama — viendo la magia de una sola pasada

Recorrido visual para nums = [2,7,11,15], objetivo = 9

Paso 0: visto = {}
Paso 1 (i=0, num=2): complemento = 7. ¿7 en visto? No. Agregamos {2:0}
Paso 2 (i=1, num=7): complemento = 2. ¿2 en visto? ¡Sí! visto[2] = 0 → devolvemos [0,1]. Listo.
Nunca siquiera miramos 11 y 15.

Es como si el algoritmo tuviera supervisión — detecta la respuesta en el momento más temprano posible.

Otros lenguajes y pequeñas variaciones

Aunque escribimos pseudocódigo estilo Python, la misma lógica aplica para JavaScript, Java, C++, etc.

Ejemplo en JavaScript (usando Map).

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) return [map.get(complement), i];
        map.set(nums[i], i);
    }
};

Ejemplo en Java (usando HashMap).

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

Trampas comunes y cómo evitarlas

• Olvidar el orden: Siempre verifica el complemento antes de almacenar el número actual. De lo contrario, podrías emparejar un elemento consigo mismo (cuando el complemento es igual al número actual).
• Usar búsqueda en arreglo en lugar de hash map: Algunos principiantes intentan usar index() o búsqueda lineal para el complemento dentro del bucle, volviendo a O(n²).
• Devolver números en lugar de índices: El problema espera índices. Verifica dos veces el formato de salida.
• Asumir que el arreglo está ordenado: No es un dato dado. Así que el método de dos punteros sin almacenar índices sería complicado.

Por qué este problema importa más allá de la entrevista

Two Sum te enseña el arte de las compensaciones. La fuerza bruta es fácil de escribir pero lenta. La versión con hash map usa un poco más de memoria pero te da velocidad. En la ingeniería del mundo real, constantemente equilibras tiempo vs. espacio. Este simple problema encapsula esa decisión fundamental. Además, el patrón de “búsqueda de complemento” aparecerá nuevamente en problemas como 3Sum, 4Sum, y muchos otros.

Referencias y lecturas adicionales

Si quieres profundizar, aquí hay algunos recursos excelentes:

• Publiqué soluciones comentadas en Python, JavaScript, C++, Go, Kotlin y Swift en GitHub (leetcode-solutions/1-two-sum en el repo lumaenaut) — la misma idea O(n) con hash map que en este post.
• Página del problema Two Sum en LeetCode — problema oficial y foros de discusión.
• Wikipedia: Tabla hash — aprende sobre la estructura de datos que usamos.
• GeeksforGeeks — Two Sum — explicaciones adicionales y código en múltiples lenguajes.
• YouTube: Two Sum por NeetCode — explicación visual (muy recomendado para aprendices visuales).
• Hoja de referencia Big-O — para entender mejor el análisis de complejidad.

Reflexiones finales

Comenzamos desde el bucle doble más ingenuo, soportamos el dolor de O(n²), y luego subimos de nivel a una solución con hash map de una pasada que es elegante, rápida y fácil de recordar. Ese es el espíritu del pensamiento algorítmico: siempre iterar, siempre optimizar, y nunca tener miedo de usar memoria extra si te da grandes ganancias de velocidad.

Two Sum puede ser tu primer problema de LeetCode, pero no será el último. Los patrones que aprendas aquí se quedarán contigo. Así que la próxima vez que veas un desafío de codificación, pregúntate: “¿Puedo usar un hash map para recordar cosas?” A menudo es la clave.

Feliz codificación, y que tu complejidad siempre sea baja.