I problemi con finestra scorrevole sono problemi in cui una finestra di dimensione fissa o variabile viene spostata attraverso una struttura dati, tipicamente un array o una stringa, per risolvere problemi in modo efficiente sulla base di sottoinsiemi continui di elementi. Questa tecnica viene utilizzata quando dobbiamo trovare sottoarray o sottostringhe in base a un determinato insieme di condizioni.

Tecnica della finestra scorrevole

Tabella dei contenuti

• Cos'è la tecnica della finestra scorrevole?
• Come utilizzare la tecnica della finestra scorrevole?
• Come identificare i problemi delle finestre scorrevoli
• Casi d'uso della tecnica della finestra scorrevole
• Problemi pratici sulla tecnica della finestra scorrevole

Cos'è la tecnica della finestra scorrevole?

Tecnica della finestra scorrevole è un metodo utilizzato per risolvere in modo efficiente problemi che implicano la definizione di a finestra O allineare nei dati di input (array o stringhe) e quindi spostare la finestra sui dati per eseguire alcune operazioni all'interno della finestra. Questa tecnica è comunemente utilizzata in algoritmi come la ricerca di sottoarray con una somma specifica, la ricerca della sottostringa più lunga con caratteri univoci o la risoluzione di problemi che richiedono una finestra di dimensione fissa per elaborare gli elementi in modo efficiente.

Facciamo un esempio per capirlo correttamente, supponiamo di avere un array di dimensioni N e anche un numero intero K. Ora dobbiamo calcolare esattamente la somma massima di un sottoarray di dimensione esatta K. Ora, come dovremmo affrontare questo problema?

Un modo per farlo è prendere ciascun sottoarray di dimensione K dall'array e scoprire la somma massima di questi sottoarray. Questo può essere fatto utilizzando cicli nidificati che si tradurranno in O(N²) Complessità temporale.

Ma possiamo ottimizzare questo approccio?

La risposta è sì, invece di prenderli ciascuno K sottoarray di dimensioni K e calcolandone la somma, possiamo semplicemente prendere un sottoarray di dimensioni K da 0 a K-1 e calcolarne la somma ora sposta il nostro intervallo uno per uno insieme alle iterazioni e aggiorna il risultato, come nella successiva iterazione aumenta la sinistra e puntatore destro e aggiorna la somma precedente come mostrato nell'immagine seguente:

Tecnica della finestra scorrevole

Ora segui questo metodo per ogni iterazione finché non raggiungiamo la fine dell'array:

Tecnica della finestra scorrevole

sistema operativo Linux

Quindi, possiamo vedere che invece di ricalcolare la somma di ciascun sottoarray di dimensione K stiamo utilizzando la finestra precedente di dimensione K e utilizzando i suoi risultati aggiorniamo la somma e spostiamo la finestra a destra spostando i puntatori a sinistra e a destra, questa operazione è ottimale perché impiegare tempo O(1) per spostare l'intervallo invece di ricalcolare.

Questo approccio di spostamento dei puntatori e calcolo dei risultati di conseguenza è noto come Tecnica della finestra scorrevole .

Come utilizzare la tecnica della finestra scorrevole?

Esistono fondamentalmente due tipologie di finestre scorrevoli:

1. Finestra scorrevole a dimensione fissa:

I passaggi generali per risolvere queste domande seguendo i passaggi seguenti:

• Trova la dimensione della finestra richiesta, ad esempio K.
• Calcola il risultato per la prima finestra, ovvero includi i primi K elementi della struttura dati.
• Quindi utilizza un ciclo per far scorrere la finestra di 1 e continuare a calcolare il risultato finestra per finestra.

2. Finestra scorrevole di dimensioni variabili:

I passaggi generali per risolvere queste domande seguendo i passaggi seguenti:

• In questo tipo di problema con la finestra scorrevole, aumentiamo il puntatore destro uno alla volta finché la nostra condizione non diventa vera.
• In qualsiasi momento, se la nostra condizione non corrisponde, riduciamo la dimensione della nostra finestra aumentando il puntatore sinistro.
• Ancora una volta, quando la nostra condizione è soddisfatta, iniziamo ad aumentare il puntatore destro e seguiamo il passaggio 1.
• Seguiamo questi passaggi finché non raggiungiamo la fine dell'array.

Come identificare i problemi delle finestre scorrevoli:

• Questi problemi generalmente richiedono la ricerca del massimo/minimo Sottoarray , Sottostringhe che soddisfano alcune condizioni specifiche.
• La dimensione del sottoarray o della sottostringa ' K' verrà fornito in alcuni dei problemi.
• Questi problemi possono essere facilmente risolti in O(N²) complessità temporale utilizzando cicli annidati, utilizzando la finestra scorrevole possiamo risolverli SU) Complessità temporale.
• Complessità temporale richiesta: O(N) o O(Nlog(N))
• Vincoli: N <= 10⁶, Se N è la dimensione della matrice/stringa.

Casi d'uso della tecnica della finestra scorrevole:

1. Per trovare la somma massima di tutti i sottoarray di dimensione K:

Dato un array di numeri interi di dimensione 'N', Il nostro obiettivo è calcolare la somma massima di 'K' elementi consecutivi dell'array.

Ingresso: arr[] = {100, 200, 300, 400}, k = 2
Produzione : 700

Ingresso: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Produzione : 39
Otteniamo la somma massima aggiungendo il sottoarray {4, 2, 10, 23} di dimensione 4.

Ingresso: arr[] = {2, 3}, k = 3
Produzione : Non valido
Non esiste un sottoarray di dimensione 3 poiché la dimensione dell'intero array è 2.

Approccio ingenuo: Quindi, analizziamo il problema con Approccio della forza bruta . Iniziamo con il primo indice e sommiamo fino al kth elemento. Lo facciamo per tutti i possibili blocchi o gruppi consecutivi di k elementi. Questo metodo richiede un ciclo for nidificato, il ciclo for esterno inizia con l'elemento iniziale del blocco di k elementi e il ciclo interno o nidificato si sommerà fino all'elemento k-esimo.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>numero2) ? num1: num2; } // Restituisce la somma massima in un sottoarray di dimensione k. int maxSum(int arr[], int n, int k) { // Inizializza il risultato int max_sum = INT_MIN;  // Considera tutti i blocchi che iniziano con i.  for (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

# code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

// C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

 // code ?>// Soluzione O(n*k) per trovare la somma massima di // un sottoarray di dimensione k // Restituisce la somma massima in un sottoarray di dimensione k. function maxSum($arr, $n, $k) { // Inizializza il risultato $max_sum = PHP_INT_MIN ; // Considera tutti i blocchi // che iniziano con i. per ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

24>

Complessità temporale: O(k*n) poiché contiene due cicli nidificati.
Spazio ausiliario: O(1)

Applicazione della tecnica della finestra scorrevole:

• Calcoliamo la somma dei primi k elementi su n termini utilizzando un ciclo lineare e memorizziamo la somma in variabile somma_finestra .
• Quindi attraverseremo linearmente l'array fino a raggiungere la fine e contemporaneamente terremo traccia della somma massima.
• Per ottenere la somma corrente di un blocco di k elementi basta sottrarre il primo elemento dal blocco precedente e aggiungere l'ultimo elemento del blocco corrente.

La rappresentazione seguente chiarirà come la finestra scorre sull'array.

Considera un array arr[] = {5, 2, -1, 0, 3} e valore di K = 3 e N = 5

Questa è la fase iniziale in cui abbiamo calcolato la somma della finestra iniziale partendo dall'indice 0 . In questa fase la somma della finestra è 6. Ora impostiamo la somma_massima come finestra_corrente, ovvero 6.

Ora facciamo scorrere la nostra finestra di un indice unitario. Pertanto ora scarta 5 dalla finestra e aggiunge 0 alla finestra. Quindi, otterremo la somma della nuova finestra sottraendo 5 e aggiungendovi 0. Quindi, la somma della finestra ora diventa 1. Ora confronteremo questa somma della finestra con la somma_massima. Dato che è più piccolo, non modificheremo il valore maxim_sum.

Allo stesso modo, ora, ancora una volta, facciamo scorrere la nostra finestra di un indice unitario e otteniamo che la nuova somma della finestra sia 2. Ancora una volta controlliamo se la somma della finestra corrente è maggiore della somma_massima fino ad ora. Ancora una volta è più piccolo quindi non modifichiamo la somma_massima.
Pertanto, per l'array precedente la nostra somma_massima è 6.

Di seguito è riportato il codice per l'approccio precedente:

// O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

# O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

// C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

>

 // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

24>

Complessità temporale: O(n), dove N è la dimensione dell'array di input arr[] .
Spazio ausiliario: O(1)

2. Sottoarray più piccolo con somma maggiore di un determinato valore:

Dato un array arr[] di numeri interi e un numero X , il compito è trovare il sottoarray più piccolo con una somma maggiore del valore specificato.

Approccio:

ricerca binaria Python

Possiamo risolvere questo problema utilizzando la tecnica della finestra scorrevole e mantenendo due puntatori: inizio e fine per contrassegnare l'inizio e la fine della finestra. Possiamo continuare a incrementare il puntatore finale finché la somma della finestra non è inferiore o uguale a X. Quando la somma della finestra diventa maggiore di X, registriamo la lunghezza della finestra e iniziamo a spostare il puntatore iniziale fino alla somma della finestra diventa minore o uguale a X. Ora, quando la somma diventa minore o uguale a X, inizia nuovamente a incrementare il puntatore finale. Continua a spostare il puntatore di inizio e fine finché non raggiungiamo la fine dell'array.

3. Trova il sottoarray con la somma data in un array di numeri interi non negativi:

Dato un array arr[] di numeri interi non negativi e un numero intero somma , trova un sottoarray che aggiunge a un dato somma .

Approccio:

L'idea è semplice poiché sappiamo che tutti gli elementi in un sottoarray sono positivi, quindi se un sottoarray ha una somma maggiore di data somma quindi non c'è alcuna possibilità che l'aggiunta di elementi al sottoarray corrente sia uguale alla somma data. Quindi l'idea è quella di utilizzare un approccio simile ad a finestra scorrevole .

• Inizia con un sottoarray vuoto.
• aggiungi elementi al sottoarray finché la somma non è inferiore a X (data la somma) .
• Se la somma è maggiore di X , rimuovi gli elementi da inizio del sottoarray corrente.

4. Finestra più piccola che contiene tutti i caratteri della stringa stessa:

Approccio:

Fondamentalmente una finestra di caratteri viene mantenuta utilizzando due puntatori in particolare inizio E FINE . Questi inizio E FINE i puntatori possono essere utilizzati rispettivamente per ridurre e aumentare la dimensione della finestra. Ogni volta che la finestra contiene tutti i caratteri di una determinata stringa, la finestra viene ridotta dal lato sinistro per rimuovere i caratteri extra e quindi la sua lunghezza viene confrontata con la finestra più piccola trovata finora.
Se nella finestra attuale non è possibile eliminare più caratteri, iniziamo ad aumentare la dimensione della finestra utilizzando il comando FINE finché tutti i caratteri distinti presenti nella stringa non saranno presenti anche nella finestra. Infine, trova la dimensione minima di ciascuna finestra.

Problemi pratici sulla tecnica della finestra scorrevole:

Articoli Correlati:

• R Articoli recenti sulla tecnica delle finestre scorrevoli
• Domande pratiche sulla finestra scorrevole
• DSA Self-paced – Il corso più utilizzato e affidabile sui DSA