lumænaut

Soluciones LeetCode
#1 — Suma de dos

De fuerza bruta a O(n)—un recorrido amigable para principiantes

Por Alberto Del Valle

(Tiempo de lectura ~4 min)

Arte ASCII a color: una computadora anticuada sobre un escritorio con una estantería al fondo, que sugiere un espacio de trabajo clásico para programar.

Enunciado del problema

Dado un arreglo de números enteros nums y un entero target, devuelve los índices de los dos números tales que su suma sea igual a 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.

Ejemplo 1:

Ejemplo 2:

Ejemplo 3:

Restricciones:

  • 2 <= nums.length <= 10⁴

  • -10⁹ <= nums[i] <= 10⁹

  • -10⁹ <= target <= 10⁹

  • Solo existe una respuesta válida.

Seguimiento: ¿Puedes idear un algoritmo con complejidad temporal a O(n²)?

El enfoque ingenuo

Podrías tomar el primer número y luego intentar sumarlo con cada número que le sigue. Si coincide con el target, ¡listo! Es simple, honesto y funciona. Pero también es una solución lenta.

Python

def twoSum_fuerzabruta(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 inicial

Si el arreglo tiene n elementos, el bucle exterior se ejecuta n veces, y el bucle interior se ejecutaría n/2 veces en promedio. Eso nos da aproximadamente n * (n-1)/2 operaciones, lo que se traduce en O(n²). Si n = 10,000... ¡eso son cerca de 50 millones de comparaciones!

Usando memoria

En lugar de comprobar cada par, podemos recordar qué números hemos visto y preguntarnos: ¿Necesito un número específico para completar el target?

Para cada número x, su complemento es target - x. Si ya hemos visto ese complemento en algún lugar del arreglo, ¡hemos encontrado nuestro par! Solo necesitamos una forma de almacenar los números por los que ya pasamos y buscarlos rápidamente. Ahí es donde entra un mapa hash (también llamado tabla hash o diccionario)—una estructura de datos que permite almacenar pares clave-valor y comprobar si una clave existe en tiempo promedio O(1).

Python

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

Sigamos el ejemplo nums = [3,2,4], target = 6:

Simulación paso a paso: nums = [3,2,4] , target = 6
Paso i num complemento vistos antes Acción vistos después
1 0 3 3 {} Guardar {3:0} {3:0}
2 1 2 4 {3:0} Guardar {2:1} {3:0, 2:1}
3 2 4 2 {3:0, 2:1} Encontrado 2 → devolver [1, 2] Terminado → [1, 2]
Cada fila corresponde a una iteración del bucle. Cuando el complemento ya existe en vistos (paso 3), devolvemos inmediatamente el par de índices.

Hermoso, ¿no es así? Solo recorremos el arreglo una vez.

Complejidad final

Complejidad temporal: O(n) — recorremos el arreglo una sola vez, y cada operación de mapa hash (inserción y búsqueda) es O(1) en promedio. Lo cual también responde a la pregunta de si podemos hacer algo mejor que O(n²).
Complejidad espacial: O(n) — en el peor de los casos almacenamos casi todos los elementos en el mapa hash antes de encontrar el par.

Feliz programación, y que tu complejidad siempre sea baja.
#2

Referencias y lecturas adicionales

¿No tienes suficiente de lumænaut? Lee esto...