Two-sum e le sue numerose varianti
Risolva two-sum, three-sum, four-sum e two-sum with sorted array usando hash map e due puntatori, confrontando i costi in termini di tempo e spazio
Two-sum e le sue numerose varianti è una lezione Coding Interview Prep 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Two-sum: il classico problema da colloquio
LeetCode 1 'Two Sum': dato un array non ordinato e un valore obiettivo, restituisca gli indici di due elementi la cui somma è uguale all'obiettivo. L'approccio a forza bruta O(n²) controlla tutte le coppie. L'approccio ottimale O(n) usa una hash map: per ogni elemento x, verifichi se target - x esiste già nella mappa. In caso affermativo, restituisca la coppia di indici. In caso contrario, memorizzi x e il suo indice nella mappa.
Two-sum è spesso il primo problema proposto durante un colloquio: conoscerlo alla perfezione dimostra che è pronto ad affrontare problemi più difficili.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Perché la hash map funziona per two-sum
La hash map memorizza ogni elemento incontrato fino a quel momento. Durante l'elaborazione dell'elemento x, se target - x è presente nella mappa, i due elementi formano una coppia valida. È fondamentale verificare sempre il complemento prima di memorizzare x: in questo modo si evita di associare un elemento a se stesso (ad esempio, se x == target/2, il controllo nella mappa avviene prima che x venga memorizzato, quindi l'elemento non corrisponderà a se stesso a meno che non ne esistano due copie).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iTwo-sum su un array ordinato (due puntatori)
Se l'array è già ordinato e Le servono gli indici dei valori (non gli indici originali), usi la tecnica dei due puntatori: i puntatori sinistro e destro partono dalle estremità opposte. Se la somma è uguale all'obiettivo, restituisca il risultato. Se la somma è troppo piccola, sposti il puntatore sinistro verso destra. Se è troppo grande, sposti il puntatore destro verso sinistra. La complessità è O(n) in termini di tempo e O(1) di spazio: è migliore dell'approccio con hash map quando l'array è ordinato e la memoria è limitata.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-sum (LeetCode 15)
LeetCode 15 'Three Sum': trovi tutte le triplette distinte la cui somma è zero. Ordini l'array, fissi un elemento alla volta e applichi il metodo dei due puntatori alla sottoarray ordinata rimanente. Salti i valori duplicati per evitare triplette duplicate. Complessità temporale: O(n²), ottimale per questo problema poiché l'output stesso può contenere O(n²) triplette.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-sum (LeetCode 18)
LeetCode 18 'Four Sum': trovi tutte le quadruple distinte la cui somma è uguale all'obiettivo. Estenda three-sum: fissi due elementi con due cicli annidati (saltando i duplicati), quindi applichi il metodo dei due puntatori alla sottoarray interna. Complessità temporale: O(n³). In generale, per k-sum, il modello consiste nel ricorrere k-2 volte e poi applicare due puntatori, con complessità O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Two-sum con somma più vicina all'obiettivo
Una variante comune consiste nel trovare la coppia con la somma più vicina all'obiettivo (che potrebbe non essere esattamente uguale). Ordini l'array e usi due puntatori. Tenga traccia della somma più vicina incontrata finora e la aggiorni ogni volta che trova una coppia con una differenza assoluta dall'obiettivo più piccola. Questo approccio, con complessità O(n log n), è semplice da applicare dopo l'ordinamento.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Two-sum con più coppie (tutte le coppie)
Per trovare tutte le coppie la cui somma è uguale a un obiettivo, ordini l'array e usi due puntatori, raccogliendo tutte le coppie. Dopo aver trovato una coppia valida, salti i duplicati da entrambe le estremità prima di continuare. Si ottiene una complessità O(n log n) per l'ordinamento più O(n) per la scansione, quindi O(n log n) complessiva. Anche l'uso di una hash map per raccogliere le coppie è valido, ma richiede attenzione nella gestione dei duplicati.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Contare le coppie con somma minore di K
Un'altra variante consiste nel contare quante coppie hanno una somma minore di k. Ordini l'array e usi due puntatori. Quando nums[lo] + nums[hi] < k, tutte le coppie (lo, lo+1), (lo, lo+2), ..., (lo, hi) sono valide: si tratta di hi - lo coppie. Avanzi lo. Altrimenti riduci hi. Il tempo totale è O(n log n) per l'ordinamento più O(n) per il conteggio.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyTwo-sum con hash map: gestione dei duplicati
Quando lo stesso valore può comparire più volte e deve contare le coppie valide (non solo verificarne l'esistenza), memorizzi nella mappa le frequenze. Per le coppie in cui i due elementi sono uguali, il numero di coppie ottenibile da una frequenza f è f*(f-1)//2. Per le coppie in cui i due elementi sono diversi, moltiplichi le rispettive frequenze. In questo modo è possibile contare tutte le coppie valide in O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Riconoscere le varianti dello schema two-sum
Lo schema two-sum si presenta in molte forme diverse. Lo riconosca quando un problema chiede di trovare due o più elementi che soddisfano una relazione numerica (somma, prodotto o differenza). La strategia di base è sempre la stessa: fissi un elemento, quindi cerchi il suo complemento in una struttura precalcolata (una hash map oppure un array ordinato con un puntatore). Estenda il metodo a k-sum fissando k-2 elementi con cicli annidati e applicando il caso base.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Comunicare durante un colloquio sul problema two-sum
Quando durante un colloquio compare two-sum, esponga ad alta voce il Suo ragionamento: «Mi servono due numeri la cui somma sia uguale all'obiettivo. Per ogni numero x devo verificare se target-x esiste. Posso rispondere in O(1) usando una hash map, ottenendo un tempo totale O(n) e uno spazio O(n). In alternativa, se l'array fosse ordinato, potrei usare due puntatori con spazio O(1)». Presenti entrambi gli approcci e chieda se ci sono vincoli di spazio prima di scegliere.
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: two-sum usa una mappa hash per verificare in O(1) l'esistenza del complemento, ottenendo O(n) complessivo, per gli array ordinati, due puntatori garantiscono uno spazio O(1) e three-sum e four-sum si riducono a two-sum tramite ordinamento e cicli annidati, con complessità rispettivamente O(n²) e O(n³). Nella prossima lezione esamineremo i pattern di conteggio delle frequenze e il raggruppamento con defaultdict e Counter.
Domande Frequenti
La lezione «Two-sum e le sue numerose varianti» è gratuita?
Sì — il testo completo di «Two-sum e le sue numerose varianti» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Two-sum e le sue numerose varianti»?
Risolva two-sum, three-sum, four-sum e two-sum with sorted array usando hash map e due puntatori, confrontando i costi in termini di tempo e spazio Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep 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 «Two-sum e le sue numerose varianti»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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
- Interni delle funzioni hash e gestione delle collisioni
- Two-sum e le sue numerose varianti
- Conteggio e raggruppamento delle frequenze
- Sequenza consecutiva più lunga e cache LRU