Schiebefensterprobleme sind Probleme, bei denen ein Fenster mit fester oder variabler Größe durch eine Datenstruktur, typischerweise ein Array oder eine Zeichenfolge, verschoben wird, um Probleme basierend auf kontinuierlichen Teilmengen von Elementen effizient zu lösen. Diese Technik wird verwendet, wenn wir Subarrays oder Teilstrings gemäß einem bestimmten Satz von Bedingungen finden müssen.

Schiebefenstertechnik

Inhaltsverzeichnis

• Was ist die Schiebefenstertechnik?
• Wie wendet man die Schiebefenstertechnik an?
• So identifizieren Sie Probleme mit Schiebefenstern
• Anwendungsfälle der Schiebefenstertechnik
• Üben Sie Aufgaben zur Schiebefenstertechnik

Was ist die Schiebefenstertechnik?

Schiebefenstertechnik ist eine Methode zur effizienten Lösung von Problemen, die die Definition von a beinhalten Fenster oder Reichweite in den Eingabedaten (Arrays oder Strings) und verschieben Sie dann dieses Fenster über die Daten, um eine Operation innerhalb des Fensters auszuführen. Diese Technik wird häufig in Algorithmen wie der Suche nach Unterarrays mit einer bestimmten Summe, der Suche nach der längsten Teilzeichenfolge mit eindeutigen Zeichen oder der Lösung von Problemen verwendet, die ein Fenster mit fester Größe erfordern, um Elemente effizient zu verarbeiten.

Um dies richtig zu verstehen, nehmen wir ein Beispiel: Angenommen, wir haben ein Array unterschiedlicher Größe N und auch eine ganze Zahl K. Jetzt müssen wir die maximale Summe eines Subarrays mit der Größe genau berechnen K. Wie sollen wir nun dieses Problem angehen?

Eine Möglichkeit, dies zu erreichen, besteht darin, jedes Subarray der Größe K aus dem Array zu nehmen und die maximale Summe dieser Subarrays zu ermitteln. Dies kann mithilfe verschachtelter Schleifen erfolgen, die zu O(N) führen²) Zeitkomplexität.

Aber können wir diesen Ansatz optimieren?

Die Antwort lautet „Ja“, anstatt jedes einzelne zu nehmen K Wir können einfach ein Subarray mit der Größe K vom Index 0 bis zum Index K-1 nehmen und seine Summe berechnen. Verschieben Sie nun unseren Bereich nacheinander zusammen mit den Iterationen und aktualisieren Sie das Ergebnis, wie in der nächsten Iteration die linke Seite und erhöhen Bewegen Sie den rechten Zeiger und aktualisieren Sie die vorherige Summe, wie im folgenden Bild gezeigt:

Schiebefenstertechnik

Befolgen Sie nun diese Methode für jede Iteration, bis wir das Ende des Arrays erreichen:

Schiebefenstertechnik

F-String-Python

Wir können also sehen, dass wir statt der Neuberechnung der Summe jedes Subarrays der Größe K das vorherige Fenster der Größe K verwenden und anhand seiner Ergebnisse die Summe aktualisieren und das Fenster nach rechts verschieben, indem wir die Zeiger nach links und rechts verschieben. Diese Operation ist optimal, weil sie Nehmen Sie sich O(1) Zeit, um den Bereich zu verschieben, anstatt ihn neu zu berechnen.

Dieser Ansatz, die Zeiger zu verschieben und die Ergebnisse entsprechend zu berechnen, wird als bezeichnet Schiebefenstertechnik .

Wie wendet man die Schiebefenstertechnik an?

Grundsätzlich gibt es zwei Arten von Schiebefenstern:

1. Schiebefenster mit fester Größe:

Die allgemeinen Schritte zur Lösung dieser Fragen sind wie folgt:

• Finden Sie die Größe des erforderlichen Fensters, sagen wir K.
• Berechnen Sie das Ergebnis für das 1. Fenster, d. h. schließen Sie die ersten K Elemente der Datenstruktur ein.
• Verwenden Sie dann eine Schleife, um das Fenster um 1 zu verschieben und das Ergebnis Fenster für Fenster weiter zu berechnen.

2. Schiebefenster mit variabler Größe:

Die allgemeinen Schritte zur Lösung dieser Fragen sind wie folgt:

• Bei dieser Art von Schiebefensterproblem erhöhen wir unseren rechten Zeiger nach und nach, bis unsere Bedingung wahr ist.
• Wenn unsere Bedingung bei jedem Schritt nicht übereinstimmt, verkleinern wir die Größe unseres Fensters, indem wir den linken Zeiger vergrößern.
• Wenn unsere Bedingung erneut erfüllt ist, beginnen wir mit der Erhöhung des rechten Zeigers und folgen Schritt 1.
• Wir befolgen diese Schritte, bis wir das Ende des Arrays erreicht haben.

So erkennen Sie Probleme mit Schiebefenstern:

• Diese Probleme erfordern im Allgemeinen die Ermittlung des Maximums/Minimums Unterarray , Teilzeichenfolgen die eine bestimmte Bedingung erfüllen.
• Die Größe des Subarrays oder Substrings K‘ wird in einigen der Aufgaben gegeben.
• Diese Probleme können leicht in O(N) gelöst werden²) Zeitkomplexität mithilfe verschachtelter Schleifen, mithilfe eines Schiebefensters können wir diese lösen An) Zeitkomplexität.
• Erforderliche Zeitkomplexität: O(N) oder O(Nlog(N))
• Einschränkungen: N <= 10⁶, Wenn N die Größe des Arrays/Strings ist.

Anwendungsfälle der Schiebefenstertechnik:

1. Um die maximale Summe aller Subarrays der Größe K zu ermitteln:

Gegeben sei ein Array von Ganzzahlen der Größe 'N', Unser Ziel ist es, die maximale Summe von zu berechnen „k“ aufeinanderfolgende Elemente im Array.

Eingabe: arr[] = {100, 200, 300, 400}, k = 2
Ausgabe : 700

Eingabe: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Ausgabe : 39
Wir erhalten die maximale Summe, indem wir das Unterarray {4, 2, 10, 23} der Größe 4 hinzufügen.

Eingabe: arr[] = {2, 3}, k = 3
Ausgabe : Ungültig
Es gibt kein Unterarray der Größe 3, da die Größe des gesamten Arrays 2 beträgt.

Naiver Ansatz: Analysieren wir also das Problem mit Brute-Force-Ansatz . Wir beginnen mit dem ersten Index und summieren bis zum kth Element. Wir machen es für alle möglichen aufeinanderfolgenden Blöcke oder Gruppen von k Elementen. Diese Methode erfordert eine verschachtelte for-Schleife. Die äußere for-Schleife beginnt mit dem Startelement des Blocks aus k Elementen und die innere oder verschachtelte Schleife wird bis zum k-ten Element aufsummiert.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

// 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; } // Gibt die maximale Summe in einem Subarray der Größe k zurück. int maxSum(int arr[], int n, int k) { // Ergebnis initialisieren int max_sum = INT_MIN;  // Betrachte alle Blöcke, die mit i beginnen.  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ösung zum Ermitteln der maximalen Summe // eines Subarrays der Größe k // Gibt die maximale Summe in einem Subarray der Größe k zurück. function maxSum($arr, $n, $k) { // Ergebnis initialisieren $max_sum = PHP_INT_MIN ; // Betrachte alle Blöcke // beginnend mit 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>

Zeitkomplexität: O(k*n), da es zwei verschachtelte Schleifen enthält.
Hilfsraum: O(1)

Anwendung der Schiebefenstertechnik:

• Wir berechnen die Summe der ersten k Elemente aus n Termen mithilfe einer linearen Schleife und speichern die Summe in einer Variablen window_sum .
• Dann durchlaufen wir das Array linear, bis es das Ende erreicht, und verfolgen gleichzeitig die maximale Summe.
• Um die aktuelle Summe eines Blocks von k Elementen zu erhalten, subtrahieren Sie einfach das erste Element vom vorherigen Block und addieren Sie das letzte Element des aktuellen Blocks.

Die folgende Darstellung macht deutlich, wie das Fenster über das Array gleitet.

Betrachten Sie ein Array arr[] = {5, 2, -1, 0, 3} und Wert von k = 3 und N = 5

Dies ist die Anfangsphase, in der wir die anfängliche Fenstersumme ausgehend vom Index 0 berechnet haben. Zu diesem Zeitpunkt beträgt die Fenstersumme 6. Jetzt setzen wir die maximale_Summe auf „aktuelles_Fenster“, also 6.

Jetzt verschieben wir unser Fenster um einen Einheitenindex. Daher verwirft es jetzt 5 aus dem Fenster und fügt 0 zum Fenster hinzu. Daher erhalten wir unsere neue Fenstersumme, indem wir 5 subtrahieren und dann 0 hinzufügen. Unsere Fenstersumme wird jetzt also 1. Jetzt vergleichen wir diese Fenstersumme mit der Maximumsumme. Da es kleiner ist, werden wir die Maximumsumme nicht ändern.

In ähnlicher Weise verschieben wir nun noch einmal unser Fenster um einen Einheitsindex und erhalten die neue Fenstersumme 2. Wieder prüfen wir, ob diese aktuelle Fenstersumme größer als die bisherige Maximumsumme ist. Auch hier ist es kleiner, sodass wir die Maximumsumme nicht ändern.
Daher beträgt unsere Maximumsumme für das obige Array 6.

Unten ist der Code für den obigen Ansatz:

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

Zeitkomplexität: O(n), wo N ist die Größe des Eingabearrays arr[] .
Hilfsraum: O(1)

2. Kleinstes Subarray mit einer Summe größer als ein gegebener Wert:

Gegeben ein Array arr[] aus ganzen Zahlen und einer Zahl X Die Aufgabe besteht darin, das kleinste Subarray zu finden, dessen Summe größer als der angegebene Wert ist.

Ansatz:

Wir können dieses Problem mithilfe der Sliding-Window-Technik lösen und zwei Zeiger beibehalten: Start und Ende, um den Anfang und das Ende des Fensters zu markieren. Wir können den Endzeiger weiter erhöhen, bis die Summe des Fensters kleiner oder gleich X ist. Wenn die Summe der Fenster größer als X wird, zeichnen wir die Länge des Fensters auf und beginnen, den Startzeiger bis zur Summe der Fenster zu bewegen kleiner oder gleich X wird. Wenn die Summe nun kleiner oder gleich X wird, beginnen Sie erneut mit der Erhöhung des Endzeigers. Bewegen Sie den Start- und Endzeiger weiter, bis wir das Ende des Arrays erreicht haben.

3. Finden Sie ein Subarray mit der angegebenen Summe in einem Array nicht negativer Ganzzahlen:

Gegeben ein Array arr[] von nichtnegativen ganzen Zahlen und einer ganzen Zahl Summe , finden Sie ein Subarray, das etwas zu einem gegebenen Array hinzufügt Summe .

Ansatz:

Die Idee ist einfach, da wir wissen, dass alle Elemente im Subarray positiv sind, wenn also die Summe eines Subarrays größer als die ist gegebene Summe Dann besteht keine Möglichkeit, dass das Hinzufügen von Elementen zum aktuellen Subarray der angegebenen Summe entspricht. Die Idee besteht also darin, einen ähnlichen Ansatz wie a zu verwenden Schiebefenster .

globale Variablen js

• Beginnen Sie mit einem leeren Subarray.
• Fügen Sie dem Subarray Elemente hinzu, bis die Summe kleiner ist als X (angegebene Summe) .
• Wenn die Summe größer ist als X , Elemente aus dem entfernen Start des aktuellen Subarrays.

4. Kleinstes Fenster, das alle Zeichen der Zeichenfolge selbst enthält:

Ansatz:

Grundsätzlich wird ein Zeichenfenster mithilfe von zwei Zeigern verwaltet Start Und Ende . Diese Start Und Ende Zeiger können verwendet werden, um das Fenster zu verkleinern bzw. zu vergrößern. Immer wenn das Fenster alle Zeichen einer bestimmten Zeichenfolge enthält, wird das Fenster von der linken Seite her verkleinert, um zusätzliche Zeichen zu entfernen, und dann wird seine Länge mit dem kleinsten bisher gefundenen Fenster verglichen.
Wenn im aktuellen Fenster keine weiteren Zeichen gelöscht werden können, beginnen wir mit der Vergrößerung des Fensters Ende bis alle in der Zeichenfolge vorhandenen eindeutigen Zeichen auch im Fenster vorhanden sind. Ermitteln Sie abschließend die Mindestgröße jedes Fensters.

Übungsaufgaben zur Schiebefenstertechnik:

In Verbindung stehende Artikel:

• R Aktuelle Artikel zur Schiebefenstertechnik
• Übungsfragen zum Schiebefenster
• DSA im Selbststudium – Der am häufigsten genutzte und vertrauenswürdige Kurs zu DSA