Sliding Window-problemer er problemer, hvor et vindue med fast eller variabel størrelse flyttes gennem en datastruktur, typisk en matrix eller streng, for at løse problemer effektivt baseret på kontinuerlige delmængder af elementer. Denne teknik bruges, når vi skal finde subarrays eller substrings i henhold til et givet sæt betingelser.

Skydevindue teknik

Indholdsfortegnelse

• Hvad er skydevindueteknik?
• Hvordan bruger man skydevindueteknik?
• Sådan identificeres problemer med glidende vinduer
• Brug eksempler på skydevindueteknik
• Øv problemer på skydevindueteknik

Hvad er skydevindueteknik?

Skydevindue teknik er en metode, der bruges til effektivt at løse problemer, der involverer at definere en vindue eller rækkevidde i inputdataene (arrays eller strenge) og derefter flytte vinduet hen over dataene for at udføre en operation i vinduet. Denne teknik bruges almindeligvis i algoritmer som at finde subarrays med en specifik sum, finde den længste understreng med unikke tegn eller løse problemer, der kræver et vindue med fast størrelse for at behandle elementer effektivt.

Lad os tage et eksempel for at forstå dette korrekt, lad os sige, at vi har en række størrelser N og også et heltal K. Nu skal vi beregne den maksimale sum af en subarray med størrelse nøjagtigt K. Hvordan skal vi nu gribe dette problem an?

En måde at gøre dette på ved at tage hver subarray af størrelse K fra arrayet og finde ud af den maksimale sum af disse subarrays. Dette kan gøres ved at bruge Nested loops, som vil resultere i O(N²) Tidskompleksitet.

Men kan vi optimere denne tilgang?

Svaret er Ja, i stedet for at tage hver K størrelse subarray og beregne dens sum, kan vi bare tage en K størrelse subarray fra 0 til K-1 indeks og beregne dens sum nu flytte vores rækkevidde én efter én sammen med iterationerne og opdatere resultatet, ligesom i næste iteration øge venstre og højre markør og opdater den forrige sum som vist på billedet nedenfor:

Skydevindue teknik

Følg nu denne metode for hver iteration, indtil vi når slutningen af ​​arrayet:

Skydevindue teknik

markdown billeder

Så vi kan se, at i stedet for at genberegne summen af ​​hver K-størrelse subarray, bruger vi tidligere vindue med størrelse K og bruger dets resultater, vi opdaterer summen og flytter vinduet til højre ved at flytte venstre og højre pointer, denne operation er optimal, fordi den tage O(1) tid til at flytte området i stedet for at genberegne.

Denne tilgang til at flytte pointerne og beregne resultaterne i overensstemmelse hermed er kendt som Skydevindue Teknik .

Hvordan bruger man skydevindueteknik?

Der er grundlæggende to typer skydevinduer:

1. Skydevindue med fast størrelse:

De generelle trin til at løse disse spørgsmål ved at følge nedenstående trin:

• Find størrelsen på det ønskede vindue, sig K.
• Beregn resultatet for 1. vindue, dvs. medtag de første K elementer i datastrukturen.
• Brug derefter en løkke til at skubbe vinduet med 1 og fortsæt med at beregne resultatet vindue for vindue.

2. Skydevindue med variabel størrelse:

De generelle trin til at løse disse spørgsmål ved at følge nedenstående trin:

• I denne type glidende vinduesproblem øger vi vores højre pointer en efter en, indtil vores tilstand er sand.
• På ethvert trin, hvis vores tilstand ikke stemmer overens, formindsker vi størrelsen af ​​vores vindue ved at øge venstre markør.
• Igen, når vores tilstand er tilfredsstillende, begynder vi at øge den rigtige pointer og følger trin 1.
• Vi følger disse trin, indtil vi når til slutningen af ​​arrayet.

Sådan identificeres problemer med glidende vinduer:

• Disse problemer kræver generelt at finde maksimum/minimum Subarray , Understrenge som opfylder en bestemt betingelse.
• Størrelsen af ​​underarrayet eller understrengen ' K' vil blive givet i nogle af problemerne.
• Disse problemer kan let løses i O(N²) tidskompleksitet ved hjælp af indlejrede loops, ved hjælp af glidende vindue, vi kan løse disse i På) Tidskompleksitet.
• Påkrævet tidskompleksitet: O(N) eller O(Nlog(N))
• Begrænsninger: N <= 10⁶, Hvis N er størrelsen af ​​matrixen/strengen.

Anvendelse af skydevindueteknik:

1. For at finde den maksimale sum af alle underarrays af størrelse K:

Givet en række heltal af størrelse 'n', Vores mål er at beregne den maksimale sum af 'k' på hinanden følgende elementer i arrayet.

Input: arr[] = {100, 200, 300, 400}, k = 2
Output: 700

Input: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Output: 39
Vi får maksimal sum ved at tilføje subarray {4, 2, 10, 23} af størrelse 4.

Input: arr[] = {2, 3}, k = 3
Output: Ugyldig
Der er ingen underarray af størrelse 3, da størrelsen af ​​hele array er 2.

Naiv tilgang: Så lad os analysere problemet med Brute Force Approach . Vi starter med det første indeks og summerer indtil kth element. Vi gør det for alle mulige på hinanden følgende blokke eller grupper af k elementer. Denne metode kræver en indlejret for-løkke, den ydre for-løkke starter med startelementet i blokken af ​​k-elementer, og den indre eller den indlejrede løkke vil summere op til det k-te element.

Nedenfor er implementeringen af ​​ovenstående tilgang:

// 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>nummer 2) ? num1 : num2; } // Returnerer maksimal sum i en undermatrix af størrelsen k. int maxSum(int arr[], int n, int k) { // Initialiser resultat int max_sum = INT_MIN;  // Overvej alle blokke, der starter med 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 ?>// O(n*k) løsning til at finde den maksimale sum af // en undermatrix af størrelse k // Returnerer den maksimale sum i en undermatrix af størrelsen k. function maxSum($arr, $n, $k) { // Initialiser resultat $max_sum = PHP_INT_MIN ; // Overvej alle blokke // startende med i. for ( $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>

Tidskompleksitet: O(k*n), da den indeholder to indlejrede løkker.
Hjælpeplads: O(1)

Anvendelse af skydevindueteknikken:

• Vi beregner summen af ​​de første k elementer ud af n led ved hjælp af en lineær sløjfe og lagrer summen i variabel vinduessum .
• Så vil vi krydse lineært over arrayet, indtil det når enden og samtidig holde styr på den maksimale sum.
• For at få den aktuelle sum af en blok af k elementer skal du trække det første element fra den forrige blok og tilføje det sidste element i den aktuelle blok.

Nedenstående repræsentation vil gøre det klart, hvordan vinduet glider hen over arrayet.

Overvej et array arr[] = {5, 2, -1, 0, 3} og værdi af k = 3 og n = 5

Dette er den indledende fase, hvor vi har beregnet den indledende vinduessum startende fra indeks 0. På dette stadium er vinduessummen 6. Nu sætter vi maksimum_sum som nuværende_vindue, dvs. 6.

Nu glider vi vores vindue efter et enhedsindeks. Derfor kasserer den nu 5 fra vinduet og tilføjer 0 til vinduet. Derfor vil vi få vores nye vinduessum ved at trække 5 fra og derefter lægge 0 til det. Så vores vinduessum bliver nu 1. Nu vil vi sammenligne denne vinduessum med maksimum_sum. Da den er mindre, ændrer vi ikke maximum_sum.

Tilsvarende glider vi nu igen vores vindue med et enhedsindeks og får den nye vinduessum til at være 2. Igen tjekker vi om denne nuværende vinduessum er større end maksimum_sum indtil nu. Endnu en gang er den mindre, så vi ændrer ikke maximum_sum.
Derfor er vores maximum_sum for ovenstående array 6.

Nedenfor er koden for ovenstående tilgang:

// 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>

Tidskompleksitet: O(n), hvor n er størrelsen af ​​input array arr[] .
Hjælpeplads: O(1)

2. Mindste underarray med sum større end en given værdi:

Givet et array arr[] af heltal og et tal x , er opgaven at finde den mindste subarray med en sum større end den givne værdi.

Nærme sig:

Vi kan løse dette problem ved at bruge Sliding Window Technique og vedligeholde to pointer: start og slut for at markere starten og slutningen af ​​vinduet. Vi kan fortsætte med at øge slutmarkøren, indtil summen af ​​vinduet er mindre end eller lig med X. Når summen af ​​vinduet bliver større end X, registrerer vi længden af ​​vinduet og begynder at flytte startmarkøren til summen af ​​vinduet bliver mindre end eller lig med X. Nu, når summen bliver mindre end eller lig med X, skal du igen begynde at inkrementere slutmarkøren. Bliv ved med at flytte start- og slutmarkøren, indtil vi har nået slutningen af ​​arrayet.

3. Find subarray med given sum i en matrix af ikke-negative heltal:

Givet et array arr[] af ikke-negative heltal og et heltal sum , find en undermatrix, der føjer til en given sum .

Nærme sig:

Ideen er enkel, da vi ved, at alle elementerne i subarray er positive, så hvis en subarray har summen større end givet sum så er der ingen mulighed for, at tilføjelse af elementer til den aktuelle subarray vil være lig med den givne sum. Så ideen er at bruge en lignende tilgang til en skydevindue .

• Start med en tom underarray.
• tilføje elementer til underarrayet, indtil summen er mindre end x (given sum) .
• Hvis summen er større end x , fjern elementer fra Start af det aktuelle underarray.

4. Mindste vindue, der indeholder alle tegn i strengen:

Nærme sig:

hvordan man læser en json-fil

Grundlæggende vedligeholdes et vindue af tegn ved at bruge to pointere nemlig Start og ende . Disse Start og ende pointere kan bruges til henholdsvis at krympe og øge størrelsen af ​​vinduet. Når vinduet indeholder alle tegn i en given streng, krympes vinduet fra venstre side for at fjerne ekstra tegn, og derefter sammenlignes dets længde med det mindste vindue, der er fundet hidtil.
Hvis der i det nuværende vindue ikke kan slettes flere tegn, begynder vi at øge størrelsen af ​​vinduet ved hjælp af ende indtil alle de distinkte tegn, der findes i strengen, også er der i vinduet. Til sidst skal du finde minimumsstørrelsen for hvert vindue.

Øv problemer med skydevindueteknik:

Relaterede artikler:

• R ecente artikler om skydevindueteknik
• Øvelsesspørgsmål om glidende vindue
• DSA Self-Paced – Det mest brugte og betroede kursus om DSA