Due puntatori: estremità opposte
Usi puntatori sinistro e destro che si muovono l'uno verso l'altro per risolvere problemi di pair-sum in array ordinati, valid-palindrome e trapping-rain-water
Due puntatori: estremità opposte è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
L'idea dei due puntatori
La tecnica dei due puntatori usa due variabili indice che si muovono l'una verso l'altra (oppure nella stessa direzione) per ridurre la necessità di cicli annidati. Invece di controllare ogni coppia in O(n²), si avanza a ogni confronto e si termina in O(n). Nella maggior parte dei casi è necessario che l'array sia prima ordinato, perché l'ordinamento consente di stabilire in quale direzione spostare ciascun puntatore in base al fatto che la somma della coppia corrente sia troppo grande o troppo piccola.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Two Sum in un array ordinato
Con un array ordinato, collocare un puntatore all'estremità sinistra (il valore più piccolo) e uno all'estremità destra (il valore più grande). Se la somma è troppo piccola, spostare il puntatore sinistro verso destra per aumentarla. Se la somma è troppo grande, spostare il puntatore destro verso sinistra per diminuirla. A ogni iterazione avanza almeno un puntatore, quindi il ciclo viene eseguito al massimo n volte: O(n) complessivo dopo l'ordinamento. È importante notare che ogni spostamento è dimostrabilmente corretto grazie all'ordinamento.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Verifica del palindromo
Una stringa è un palindromo se si legge allo stesso modo in avanti e all'indietro. Usare due puntatori che partono dalle estremità opposte e si spostano verso il centro: confrontare i caratteri, saltare quelli non alfanumerici e fermarsi quando i puntatori si incrociano. L'algoritmo richiede tempo O(n) e spazio aggiuntivo O(1), risultando molto più pulito rispetto a invertire la stringa e confrontarla, operazione che alloca O(n) di memoria aggiuntiva.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseThree Sum: ordinamento + due puntatori
Three Sum richiede tutte le triplette univoche la cui somma è zero. Ordinare l'array, quindi fissare ogni elemento nums[i] ed eseguire una ricerca con due puntatori nel sottoarray rimanente per trovare una coppia la cui somma sia -nums[i]. Saltare i duplicati sia dell'elemento fissato sia della coppia trovata per evitare triplette ripetute. Tempo totale: O(n²) dopo un ordinamento O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Contenitore con più acqua
Date le altezze di linee verticali, trovare due linee che formino un contenitore capace di contenere la maggior quantità d'acqua. Area = min(height[left], height[right]) × (right - left). Spostare avidamente verso l'interno il puntatore che si trova sulla linea più corta: spostare quello sulla linea più alta può soltanto ridurre la larghezza senza aumentare il limite imposto dall'altezza. Questa scelta greedy è dimostrabilmente ottimale e consente di ottenere tempo O(n).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Elevare al quadrato un array ordinato
Elevare al quadrato ogni elemento di un array ordinato (che può contenere valori negativi) e restituire il risultato in ordine crescente. I quadrati dei valori negativi sono grandi, mentre quelli dei valori positivi sono piccoli verso il centro. Collocare due puntatori alle estremità opposte e riempire l'array risultato da destra a sinistra (dal più grande al più piccolo). Tempo O(n) e spazio O(n) per l'output: molto meglio che elevare al quadrato e poi ordinare in O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Acqua piovana intrappolata
L'acqua intrappolata all'indice i è uguale a min(max_left, max_right) - height[i]. Approccio con due puntatori: mantenere i valori progressivi max_left e max_right. Quando max_left < max_right, il lato sinistro è il collo di bottiglia: elaborare il puntatore sinistro. Altrimenti, elaborare quello destro. In questo modo non servono array separati per il massimo a sinistra e il massimo a destra, ottenendo spazio aggiuntivo O(1).
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Perché funziona lo spostamento greedy del puntatore
Una domanda frequente nei colloqui è: perché è sicuro scartare il puntatore più piccolo? Schema della dimostrazione per il problema del contenitore con più acqua: supponiamo che height[left] < height[right]. Ogni coppia (left, j) per j < right ha un'area ≤ height[left] × (j-left) < height[left] × (right-left) ≤ area corrente. Pertanto, nessuna coppia che inizi da 'left' e abbia un indice destro inferiore a 'right' può superare l'area corrente. È sicuro ignorarle facendo avanzare left.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Coppia con differenza minima in un array ordinato
Trovi la coppia di numeri in un array ordinato con la differenza assoluta più piccola. Usi due puntatori adiacenti (non alle estremità opposte) che scorrono insieme: |nums[i] - nums[i+1]| per tutte le coppie consecutive. In un array ordinato, la differenza minima si verifica sempre tra elementi adiacenti, perché l'ordinamento raggruppa i valori vicini. Questo richiede O(n) dopo l'ordinamento.
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Modello dei due puntatori alle estremità opposte
La maggior parte dei problemi con due puntatori alle estremità opposte segue la stessa struttura di base. Padroneggiare questo modello Le permette di adattarlo rapidamente anche sotto pressione. Le decisioni fondamentali sono: (1) quale condizione fa avanzare left, (2) quale condizione fa avanzare right, (3) cosa costituisce una soluzione e (4) come gestire i duplicati. Si eserciti a ricavare queste decisioni dal testo del problema prima di scrivere il codice.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultConteggio delle coppie valide con due puntatori
Anche i due puntatori consentono di contare le coppie in modo efficiente. Per il problema «contare le coppie con somma < target» in un array ordinato: fissi il puntatore left e usi il puntatore right per trovare l'indice right valido più a destra. Tutte le coppie (left, da left+1 a right) sono valide: aggiunga right - left al conteggio e faccia avanzare left. In questo modo conta tutte le coppie valide in O(n) anziché in O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Verifica 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 appreso che: i due puntatori alle estremità opposte sostituiscono l'enumerazione delle coppie in O(n²) con una convergenza da sinistra a destra in O(n) negli array ordinati, la scelta del puntatore da far avanzare deriva dalla proprietà monotona del problema: si fa avanzare il lato che al momento limita il progresso e three-sum, container-with-most-water, trapping rain water e la verifica dei palindromi si riconducono tutti allo stesso modello di base. Ora esamineremo i modelli con due puntatori slow-fast.
Domande Frequenti
La lezione «Due puntatori: estremità opposte» è gratuita?
Sì — il testo completo di «Due puntatori: estremità opposte» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Due puntatori: estremità opposte»?
Usi puntatori sinistro e destro che si muovono l'uno verso l'altro per risolvere problemi di pair-sum in array ordinati, valid-palindrome e trapping-rain-water Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 3 di 4.
Quanto tempo richiede la lezione «Due puntatori: estremità opposte»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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
- Basi degli array e operazioni in-place
- Somme prefisse e totali progressivi
- Due puntatori: estremità opposte
- Due puntatori: lento e veloce