Trovare una coppia con una somma data
Superare la forza bruta O(n^2)
Trovare una coppia con una somma data è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il problema della coppia con somma target
Dato un array e un target, occorre trovare due valori la cui somma sia uguale a esso. È uno dei problemi introduttivi più comuni nelle gare. 🔍
Il metodo della forza bruta
La soluzione più ovvia prova ogni coppia usando due cicli annidati. Funziona, ma verificare tutte le coppie costa O(n^2) e può essere decisamente troppo lento.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Dove la forza bruta non basta
Con n vicino a 100000, O(n^2) significa dieci miliardi di verifiche e si incorrerà in un TLE. I vincoli indicano che occorre trovare una soluzione più rapida.
Ordinare, poi scorrere
Se si ordina prima l'array, due puntatori alle estremità risolvono il problema con un'unica scansione. L'ordinamento costa O(n log n), mentre la scansione costa O(n).
a.sort()
left, right = 0, len(a) - 1Confrontare con il target
A ogni passaggio si legge a[left] + a[right]. Questo unico numero determina lo spostamento successivo, senza bisogno di procedere per tentativi.
total = a[left] + a[right]Corrispondenza esatta: fatto
Se la somma è uguale al target, si è trovata la coppia. La si può restituire immediatamente, poiché è sufficiente una sola risposta valida.
if total == target:
return (left, right)In caso contrario, regolare i puntatori
Se la somma è troppo piccola, si sposta left verso destra; se è troppo grande, si sposta right verso sinistra. L'ordine crescente garantisce che ogni spostamento sia utile.
elif total < target:
left += 1
else:
right -= 1Nessuna coppia esistente
Se i puntatori si incrociano senza trovare una corrispondenza, non esiste alcuna coppia valida. La fine del ciclo costituisce già una risposta completa.
L'alternativa dell'hash set
Se è necessario mantenere gli indici originali, un hash set è più semplice: per ogni valore, si verifica se il target meno quel valore è già stato visto.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Scegliere il metodo
Si usano i due puntatori quando l'array è o può essere ordinato; si usa l'hash set quando serve davvero O(n) senza ordinare o quando è necessario conservare gli indici.
Attenzione ai duplicati
Se un valore può essere abbinato a se stesso, occorre assicurarsi che i due indici siano diversi. Un rapido controllo left != right o i != j evita questo errore.
Verifica rapida
Si vuole superare la soluzione a forza bruta O(n^2) per trovare una coppia la cui somma sia uguale a un target.
Riepilogo
Si ordina l'array e poi lo si scorre con due puntatori per trovare una coppia con somma target in O(n log n), oppure si usa un hash set per ottenere O(n) quando gli indici sono importanti. La scelta dipende dai vincoli. ✅
Domande Frequenti
La lezione «Trovare una coppia con una somma data» è gratuita?
Sì — il testo completo di «Trovare una coppia con una somma data» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Trovare una coppia con una somma data»?
Superare la forza bruta O(n^2) Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Trovare una coppia con una somma data»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Due puntatori su un array ordinato
- Trovare una coppia con una somma data
- Rimuovere i duplicati sul posto
- Unire due sequenze ordinate