Pensamiento algorítmico · pares

¿Existe la suma de dos?

El calentamiento clásico de entrevistas. Recorre i por cada elemento, j desde i+1 para no emparejar un número consigo mismo, y comprueba a[i] + a[j] == T.

En una fraseRecorre i por cada elemento y j desde i+1 para no emparejar un número consigo mismo; si algún par suma T imprime yes, y el doble bucle basta para N ≤ 100.

El problema

Entrada: primera línea N (1 ≤ N ≤ 100); segunda línea N enteros; tercera línea el objetivo T.

Salida: yes si alguna dos números distintos suman T, si no no.

Ejemplos:

EntradaSalida
4
1 2 3 4
5		yes
3
1 2 3
7		no
5
10 20 30 40 50
60		yes

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — índices distintos, no valores distintos

Usa dos índices i y j con j > i. Eso garantiza dos posiciones distintas — así [3, 3] con objetivo 6 todavía cuenta (las posiciones difieren), que es lo que suelen significar "dos números" en estos problemas.

Pista 2 — detente en cuanto sepas

No necesitas probar cada par — en cuanto encuentres uno, imprime yes y terminas. Si los bucles terminan sin coincidencia, imprime no. Una bandera bool evita imprimir dos veces.

Solución (¡inténtalo primero!) 
#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    bool ok = false;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) ok = true;
    cout << (ok ? "yes" : "no") << endl;
    return 0;
}

Las entrevistas reales piden los índices, o quieren O(N) con un conjunto hash — pero la versión O(N²) es la base. Siguiente: El segundo mayor mantiene la misma idea de "lleva los valores mientras recorres".

Análisis profundo

Por qué funciona

La búsqueda de un par es el ejemplo completo más pequeño de «probar todas las combinaciones»: dos índices, una desigualdad que los mantiene distintos, una comparación. Todo algoritmo O(N²) que veas después es esta forma a escala.

El coste

O(N²) de tiempo (10.000 comprobaciones con N=100: instantáneo), O(N) de espacio para el array. Puedes salir antes del primer acierto, pero el peor caso sigue siendo un recorrido completo.

Dónde falla

  • Empezar j en 0 en vez de i+1 permite que un elemento se empareje consigo mismo: [5] con objetivo 10 respondería yes con un solo elemento.
  • Imprimir dentro del bucle: sale yes varias veces, y en los casos no no sale nada; el juez rechaza esa salida.

Siguiente paso

Pide los índices en vez de yes/no, luego ordena y usa dos punteros: el mismo problema en O(N log N). El segundo mayor mantiene el hábito de «llevar la cuenta mientras recorres».

Dos cosas para recordar

  • j empieza en i+1: posiciones distintas, nunca el mismo elemento dos veces.
  • Decide y luego imprime una sola vez: imprimir dentro de un bucle de búsqueda multiplica la salida.
🐞 Esta versión falla: ábrela y pruébala

Imprime dentro del bucle: varias líneas yes, y nada en los casos no

#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) cout << "yes" << endl;   // prints per match
    return 0;
}