Metodo dei due puntatori

2.1 Definizione del metodo dei due puntatori.

Metodo dei due puntatori — è una tecnica utilizzata per risolvere vari problemi su array e stringhe, utilizzando due puntatori (indici) che si spostano sui dati secondo regole specifiche. Questo metodo permette di risolvere in modo efficiente problemi relativi alla ricerca di coppie di elementi, sottoinsiemi, soddisfacenti condizioni date.

Questo metodo prevede l'uso di due puntatori che di solito sono inizializzati ai lati opposti della struttura dati e si muovono l'uno verso l'altro o secondo una regola specifica. Il metodo dei due puntatori può ridurre significativamente la complessità temporale dell'algoritmo rispetto a approcci più ingenui.

Principi fondamentali

1. Inizializzazione dei due puntatori: I puntatori possono essere impostati all'inizio e alla fine dell'array o della stringa, o su indici diversi a seconda del problema.
2. Spostamento dei puntatori: I puntatori si muovono secondo una regola specifica (ad esempio, entrambi i puntatori si muovono verso il centro, o un puntatore si muove in avanti mentre l'altro rimane fermo).
3. Verifica della condizione: A ogni passo viene verificata una condizione che determina l'ulteriore spostamento dei puntatori o la conclusione dell'algoritmo.

Complessità temporale:

O(n) — nella maggior parte dei casi, poiché entrambi i puntatori attraversano l'array una o più volte, ma non più di O(n) iterazioni in totale.

Per alcuni problemi, a seconda delle condizioni e delle posizioni iniziali dei puntatori, la complessità temporale può essere O(n log n) o O(n^2), ma è raro.

Esempi di problemi risolti con il metodo dei due puntatori:

2.2 Trovare due numeri in un array la cui somma è uguale a un numero dato.

Problema:

Trovare due numeri in un array ordinato che sommati diano un numero dato target.

Soluzione:

Inizializziamo un puntatore all'inizio dell'array, l'altro alla fine. Verifichiamo la somma degli elementi sotto i puntatori:

• Se la somma è uguale a target, ritorniamo gli indici.
• Se la somma è minore di target, spostiamo il puntatore sinistro a destra.
• Se la somma è maggiore di target, spostiamo il puntatore destro a sinistra.

Complessità temporale: O(n).

Esempio di codice in Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Verifica se una stringa è un palindromo

Problema:

Verificare se una stringa è un palindromo.

Soluzione:

Inizializziamo i puntatori all'inizio e alla fine della stringa. Confrontiamo i caratteri sotto i puntatori:

• Se i caratteri sono uguali, spostiamo entrambi i puntatori l'uno verso l'altro.
• Se i caratteri non sono uguali, la stringa non è un palindromo.

Complessità temporale: O(n).

Esempio di codice in Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Rimozione dei duplicati da un array ordinato

Problema:

Rimuovere i duplicati da un array ordinato.

Soluzione:

Usiamo due puntatori, uno per la posizione corrente nell'array risultante, l'altro per scorrere tutti gli elementi:

• Se l'elemento corrente non è uguale al precedente, lo scriviamo nell'array risultante.

Complessità temporale: O(n).

Esempio di codice in Python:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index