Encuentre un par con una suma dada
Supere la fuerza bruta O(n^2)
Encuentre un par con una suma dada es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
El problema de la suma de pares
Dado un arreglo y un objetivo, encuentre dos valores que sumen ese objetivo. Es una de las tareas introductorias más comunes en los concursos. 🔍
El método de fuerza bruta
La solución obvia prueba cada par mediante dos bucles anidados. Funciona, pero comprobar todos los pares cuesta O(n^2) y puede ser demasiado lento.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Dónde falla la fuerza bruta
Con n cercano a 100000, O(n^2) supone diez mil millones de comprobaciones y obtendrá un TLE. Las restricciones le indican que debe encontrar algo más rápido.
Ordene y luego recorra
Si primero ordena el arreglo, dos punteros desde ambos extremos resuelven el problema en un solo recorrido. Ordenar cuesta O(n log n) y después el recorrido cuesta O(n).
a.sort()
left, right = 0, len(a) - 1Compare con el objetivo
En cada paso, lea a[left] + a[right]. Ese único número decide el siguiente movimiento sin necesidad de adivinar.
total = a[left] + a[right]Coincidencia exacta: terminado
Si la suma es igual al objetivo, ha encontrado el par. Devuélvalo de inmediato, ya que solo necesita una respuesta válida.
if total == target:
return (left, right)De lo contrario, ajuste
Si la suma es demasiado pequeña, mueva left hacia la derecha; si es demasiado grande, mueva right hacia la izquierda. El orden garantiza que cada movimiento ayuda.
elif total < target:
left += 1
else:
right -= 1No existe ningún par
Si los punteros se cruzan sin encontrar una coincidencia, no existe ningún par válido. El final del bucle constituye por sí mismo una respuesta completa.
La alternativa del conjunto hash
Si debe conservar los índices originales, un conjunto hash resulta más sencillo: para cada valor, compruebe si ya se había visto target menos ese valor.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Elegir el método
Use dos punteros cuando el arreglo esté ordenado o pueda ordenarse; use el conjunto hash cuando necesite un O(n) real sin ordenar o deba conservar los índices.
Tenga cuidado con los duplicados
Si un valor puede formar un par consigo mismo, asegúrese de que los dos índices sean distintos. Una comprobación rápida left != right o i != j evita ese error.
Comprobación rápida
Quiere superar la fuerza bruta O(n^2) para encontrar un par cuya suma sea igual a un objetivo.
Repaso
Ordene y recorra con dos punteros para encontrar un par objetivo en O(n log n), o use un conjunto hash para obtener O(n) cuando los índices sean importantes. Elija según las restricciones. ✅
Preguntas frecuentes
¿La lección «Encuentre un par con una suma dada» es gratis?
Sí — el texto completo de «Encuentre un par con una suma dada» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Encuentre un par con una suma dada»?
Supere la fuerza bruta O(n^2) Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Encuentre un par con una suma dada»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Dos punteros en un array ordenado
- Encuentre un par con una suma dada
- Elimine duplicados en el propio array
- Combine dos secuencias ordenadas