Metodo finestra scorrevole

3.1 Definizione del metodo finestra scorrevole.

Metodo finestra scorrevole (Sliding Window) — è una tecnica usata per risolvere problemi su array o stringhe, dove un sottoarray (o sottostringa) fisso si muove sui dati per trovare una soluzione ottimale. Questo permette di elaborare gli elementi in una finestra di dimensioni fisse e di cambiare dinamicamente la finestra a seconda delle condizioni del problema.

Questa tecnica è particolarmente utile per problemi legati a sequenze di dati, come array o stringhe, e aiuta a ridurre la complessità temporale rispetto agli approcci più ingenui.

Principi principali

• Inizializzazione della finestra: Imposta l'inizio e la fine della finestra nelle posizioni iniziali.
• Spostamento della finestra: Sposta sequenzialmente i confini della finestra, aggiungendo elementi da un lato e rimuovendo elementi dall'altro.
• Elaborazione della finestra: A ogni passo, esegui i calcoli necessari per la finestra corrente.

Complessità temporale e spaziale del metodo finestra scorrevole

Complessità temporale:

• O(n) — nella maggior parte dei casi, poiché il puntatore o la finestra si muove linearmente sull'array, controllando ogni possibile posizione della finestra.

Complessità spaziale:

• O(1) — se viene utilizzato un numero fisso di memoria aggiuntiva per memorizzare i valori correnti.
• O(k) — se è necessario memorizzare gli elementi all'interno della finestra corrente di dimensione k.

3.2 Trovare la somma massima del sottoarray.

Trovare la somma massima di un sottoarray di dimensioni fisse

Compito:

Trovare il sottoarray di dimensioni fisse k con la somma massima.

Soluzione:

Usiamo il metodo finestra scorrevole per mantenere la somma corrente del sottoarray e aggiorniamo la somma massima mentre spostiamo la finestra.

Complessità temporale: O(n).

Esempio di codice in Python:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Ricerca di tutti gli anagrammi di una sottostringa in una stringa

Compito:

Trovare tutti gli anagrammi di una data sottostringa p in una stringa s.

Soluzione:

Usiamo il metodo finestra scorrevole per mantenere un dizionario di frequenza dei caratteri della finestra corrente e lo confrontiamo con il dizionario di frequenza della sottostringa.

Complessità temporale: O(n).

Esempio di codice in Python:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Trovare il sottoarray minimo

Trovare il sottoarray minimo con somma superiore a un dato valore

Compito:

Trovare il sottoarray minimo con una somma di elementi superiore a un dato valore S.

Soluzione:

Usiamo il metodo finestra scorrevole per espandere il confine destro fino a quando la somma non supera S, quindi spostiamo il confine sinistro per minimizzare la lunghezza del sottoarray.

Complessità temporale: O(n).

Esempio di codice in Python:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len