Sliding Window-problem är problem där ett fönster med fast eller variabel storlek flyttas genom en datastruktur, vanligtvis en array eller sträng, för att lösa problem effektivt baserat på kontinuerliga delmängder av element. Den här tekniken används när vi behöver hitta delarrayer eller delsträngar enligt en given uppsättning villkor.

Teknik för skjutfönster

Innehållsförteckning

• Vad är skjutfönsterteknik?
• Hur använder man skjutfönstertekniken?
• Hur man identifierar problem med skjutfönster
• Använd fall av skjutfönsterteknik
• Öva problem på skjutfönsterteknik

Vad är skjutfönsterteknik?

Teknik för skjutfönster är en metod som används för att effektivt lösa problem som innebär att definiera en fönster eller räckvidd i inmatningsdata (matriser eller strängar) och flytta sedan det fönstret över data för att utföra en operation i fönstret. Den här tekniken används ofta i algoritmer som att hitta delarrayer med en specifik summa, hitta den längsta delsträngen med unika tecken eller lösa problem som kräver ett fönster med fast storlek för att bearbeta element effektivt.

Låt oss ta ett exempel för att förstå detta korrekt, säg att vi har en mängd olika storlekar N och även ett heltal K. Nu måste vi beräkna den maximala summan av en subarray som har storlek exakt K. Hur ska vi nu närma oss detta problem?

Ett sätt att göra detta genom att ta varje delmatris av storlek K från matrisen och ta reda på den maximala summan av dessa delmatriser. Detta kan göras med kapslade loopar som kommer att resultera i O(N²) Tidskomplexitet.

Men kan vi optimera detta tillvägagångssätt?

Svaret är Ja, istället för att ta var och en K storlek underarray och beräkna dess summa, vi kan bara ta en K storlek subarray från 0 till K-1 index och beräkna dess summa nu flytta vårt intervall en efter en tillsammans med iterationerna och uppdatera resultatet, som i nästa iteration öka vänster och högerpekare och uppdatera den tidigare summan som visas i bilden nedan:

Teknik för skjutfönster

Följ nu denna metod för varje iteration tills vi når slutet av arrayen:

Teknik för skjutfönster

bias och varians

Så vi kan se att istället för att räkna om summan av varje K-stor delmatris använder vi tidigare fönster av storlek K och använder dess resultat uppdaterar vi summan och flyttar fönstret åt höger genom att flytta pekarna till vänster och höger, denna operation är optimal eftersom den ta O(1) tid att flytta intervallet istället för att räkna om.

Detta tillvägagångssätt att flytta pekarna och beräkna resultaten i enlighet därmed kallas Skjutfönster Teknik .

Hur använder man skjutfönstertekniken?

Det finns i princip två typer av skjutfönster:

1. Skjutfönster med fast storlek:

De allmänna stegen för att lösa dessa frågor genom att följa stegen nedan:

• Hitta storleken på fönstret som krävs, säg K.
• Beräkna resultatet för det första fönstret, dvs inkludera de första K elementen i datastrukturen.
• Använd sedan en slinga för att skjuta fönstret med 1 och fortsätt beräkna resultatet fönster för fönster.

2. Skjutfönster med variabel storlek:

De allmänna stegen för att lösa dessa frågor genom att följa stegen nedan:

• I den här typen av problem med skjutfönster ökar vi vår högra pekare en efter en tills vårt tillstånd är sant.
• I vilket steg som helst om vårt tillstånd inte stämmer överens, krymper vi storleken på vårt fönster genom att öka vänster pekare.
• Återigen, när vårt tillstånd är tillfredsställande börjar vi öka den högra pekaren och följer steg 1.
• Vi följer dessa steg tills vi når slutet av arrayen.

Så här identifierar du problem med skjutfönster:

• Dessa problem kräver i allmänhet Hitta max/minimum Subarray , Delsträngar som uppfyller något specifikt villkor.
• Storleken på undermatrisen eller understrängen ' K' kommer att ges i några av problemen.
• Dessa problem kan enkelt lösas i O(N²) tidskomplexitet med hjälp av kapslade loopar, med hjälp av glidande fönster kan vi lösa dessa i På) Tidskomplexitet.
• Erforderlig tidskomplexitet: O(N) eller O(Nlog(N))
• Begränsningar: N <= 10⁶, Om N är storleken på Array/String.

Användningsfall av skjutfönsterteknik:

1. För att hitta den maximala summan av alla undergrupper av storlek K:

Givet en uppsättning heltal av storlek 'n', Vårt mål är att beräkna den maximala summan av 'k' på varandra följande element i arrayen.

Inmatning : arr[] = {100, 200, 300, 400}, k = 2
Utgång: 700

Inmatning : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Utgång: 39
Vi får maximal summa genom att lägga till subarray {4, 2, 10, 23} av storlek 4.

Inmatning : arr[] = {2, 3}, k = 3
Utgång: Ogiltig
Det finns ingen undermatris av storlek 3 eftersom storleken på hela matrisen är 2.

Naivt förhållningssätt: Så låt oss analysera problemet med Brute Force Approach . Vi börjar med det första indexet och summerar till kth element. Vi gör det för alla möjliga på varandra följande block eller grupper av k element. Denna metod kräver en kapslad för-loop, den yttre for-loopen börjar med startelementet i blocket av k element, och den inre eller kapslade loopen kommer att läggas ihop till det k:te elementet.

Nedan är implementeringen av ovanstående tillvägagångssätt:

// 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>num2) ? num1: num2; } // Returnerar maximal summa i en delmatris med storleken k. int maxSum(int arr[], int n, int k) { // Initiera resultat int max_sum = INT_MIN;  // Betrakta alla block som börjar med i.  för (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 för att hitta den maximala summan av // en delmatris av storlek k // Returnerar maximal summa i en delmatris med storleken k. function maxSum($arr, $n, $k) { // Initiera resultat $max_sum = PHP_INT_MIN ; // Betrakta alla block // som börjar med i. för ( $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>

Tidskomplexitet: O(k*n) eftersom den innehåller två kapslade slingor.
Hjälputrymme: O(1)

hur man kör skriptet i linux

Använda skjutfönstertekniken:

• Vi beräknar summan av de första k elementen av n termer med hjälp av en linjär loop och lagrar summan i variabel fönstersumma .
• Sedan kommer vi att gå linjärt över matrisen tills den når slutet och samtidigt hålla reda på den maximala summan.
• För att få den aktuella summan av ett block av k element, subtrahera bara det första elementet från föregående block och addera det sista elementet i det aktuella blocket.

Representationen nedan kommer att göra det tydligt hur fönstret glider över arrayen.

Överväg en array arr[] = {5, 2, -1, 0, 3} och värdet på k = 3 och n = 5

Detta är den inledande fasen där vi har beräknat den initiala fönstersumman från index 0 . I detta skede är fönstersumman 6. Nu ställer vi in ​​maximum_summa som current_window, dvs. 6.

Nu skjuter vi vårt fönster med ett enhetsindex. Därför kastar den nu 5 från fönstret och lägger till 0 till fönstret. Därför kommer vi att få vår nya fönstersumma genom att subtrahera 5 och sedan lägga till 0 till den. Så vår fönstersumma blir nu 1. Nu kommer vi att jämföra denna fönstersumma med maximum_summa. Eftersom den är mindre kommer vi inte att ändra maximum_sum.

På samma sätt, nu förskjuter vi återigen vårt fönster med ett enhetsindex och får den nya fönstersumman till 2. Återigen kontrollerar vi om denna nuvarande fönstersumma är större än maximum_summen hittills. Återigen är den mindre så vi ändrar inte maximum_sum.
Därför är vår maximum_summa 6 för ovanstående array.

Nedan är koden för ovanstående tillvägagångssätt:

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

Tidskomplexitet: O(n), var n är storleken på inmatningsmatrisen arr[] .
Hjälputrymme: O(1)

2. Minsta delmatris med summa som är större än ett givet värde:

Givet en array arr[] av heltal och ett tal X , uppgiften är att hitta den minsta delmatrisen med en summa som är större än det givna värdet.

Närma sig:

Vi kan lösa detta problem med hjälp av Sliding Window Technique och bibehålla två pekare: start och slut för att markera början och slutet av fönstret. Vi kan fortsätta att öka slutpekaren tills summan av fönstret är mindre än eller lika med X. När summan av fönstret blir större än X, registrerar vi längden på fönstret och börjar flytta startpekaren till summan av fönstret blir mindre än eller lika med X. Nu, när summan blir mindre än eller lika med X, börja återigen öka slutpekaren. Fortsätt att flytta start- och slutpekaren tills vi har nått slutet av arrayen.

3. Hitta delmatris med given summa i en matris med icke-negativa heltal:

Givet en array arr[] av icke-negativa heltal och ett heltal belopp , hitta en undermatris som läggs till en given belopp .

Närma sig:

Idén är enkel eftersom vi vet att alla element i delmatrisen är positiva, så om en delmatris har summan större än given summa då finns det ingen möjlighet att lägga till element till den aktuella subarrayen kommer att vara lika med den givna summan. Så tanken är att använda ett liknande tillvägagångssätt till en glidande fönster .

• Börja med en tom undergrupp.
• lägg till element i subarrayen tills summan är mindre än x (given summa) .
• Om summan är större än x , ta bort element från Start av den aktuella undergruppen.

4. Minsta fönster som innehåller alla tecken i själva strängen:

Närma sig:

I princip upprätthålls ett teckenfönster genom att använda två pekare, nämligen Start och slutet . Dessa Start och slutet pekare kan användas för att krympa respektive öka storleken på fönstret. Närhelst fönstret innehåller alla tecken i en given sträng, krymps fönstret från vänster sida för att ta bort extra tecken och sedan jämförs dess längd med det minsta fönstret som hittats hittills.
Om inga fler tecken kan raderas i det aktuella fönstret börjar vi öka storleken på fönstret med hjälp av slutet tills alla distinkta tecken som finns i strängen också finns där i fönstret. Slutligen, hitta minimistorleken för varje fönster.

Öva problem med skjutfönsterteknik:

Relaterade artiklar:

• R ecenta artiklar om skjutfönsterteknik
• Övningsfrågor om skjutfönster
• DSA Self-Paced – Den mest använda och betrodda kursen om DSA