In diesem zweiten Teil unserer Serie tauchen wir in eines der vielseitigsten Muster für die Lösung von Coding -Interviewfragen ein: das Schiebenfenster. Diese Technik ist unglaublich nützlich, um Probleme zu optimieren, die Subtarrays oder Substrings von zusammenhängenden Elementen betreffen, z. B. die Maximierung der Summen, das Finden spezifischer Bedingungen innerhalb einer Sequenz oder das Arbeiten mit Substrings in Strings.

Bevor wir beginnen, sollten Sie nach einem umfassenden Leitfaden für Coding-Interviews suchen, um das Coding-Interview zu überprüfen, ein Muss für alle, die es ernst meinen, einen Job bei Top-Tech-Unternehmen zu erledigen.

Überblick über das Schiebfenstermuster

Das Schiebenfenstermuster ist eine Technik, mit der Sie Probleme effizient lösen können. Anstatt die Teilmenge jedes Mal neu zu berechnen, wenn Sie das Fenster bewegen, behält diese Technik eine laufende Gesamt- oder Bedingung bei und rutscht über die Daten, um unnötige Arbeiten zu minimieren.

Wann kann man Schiebebefenster verwenden:

• Das Problem beinhaltet zusammenhängende Subtarrays oder Substrings.
• Sie müssen die maximale oder minimale Summe, Zählung oder andere Bedingungen in einem Schiebebereich des Datensatzes finden.
• Es beinhaltet eine feste Fenstergröße oder erfordert ein dynamisches Fenster, das erweitert oder schrumpft.

---

Arten von Gleitfenster nähern sich

1. Sliding Window wurde festgestellt

• was es ist : ein Fenster einer festen Größe, die über das Array oder eine Zeichenfolge gleitet, während eine laufende Bedingung wie Summe oder Produkt beibehält.
• Beispiel : finde die maximale Summe einer Subtarray von Größe k.

Beispiel Problem : Finden Sie eine Reihe von Ganzzahlen und eine Nummer k, finden Sie die maximale Summe eines Teilestiers der Größe k.

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum  = arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum  = arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

Erläuterung:

• Ein Fenster der Größe k wird initialisiert.
• Wenn sich das Fenster über das Array bewegt, wird der Gleiteffekt erreicht, indem das Element subtrahiert, das nicht mehr im Fenster ist, und das neue Element hinzuzufügen, das das Fenster eingibt.
• Dies optimiert das Problem von einem Brute -Force -Ansatz von o (n*k) zu o (n), da wir das gesamte Fenster für jede Iteration nicht mehr zusammenfassen müssen.

---

2. Dynamisches Schiebebefenster

• was es ist : Dies wird verwendet, wenn die Fenstergröße nicht behoben ist. Das Fenster erweitert oder Verträge basierend auf den Anforderungen des Problems (wie die Befriedigung einer Summe oder Bedingung).
• example : finde die kleinste Subtarray mit einer Summe, die größer als oder gleich s.

Beispiel problem : Finden Sie die kleinste zusammenhängende Subtarray, deren Summe größer als oder gleich s.
, um eine Reihe von Ganzzahlen und eine Nummer s zu finden.

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum  = arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start   1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start  = 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

def smallest_subarray_with_sum (arr, s): # Variablen initialisieren: # window_sum: So speichern die Summe des aktuellen Fensters. # min_length: Um die Länge der kleinsten Subarray zu speichern. # window_start: Der Startindex des Schiebebefensters. window_sum = 0 min_length = float ('inf') # Beginnen Sie mit einer großen Zahl, um die Mindestlängen zu vergleichen. window_start = 0 # Über das Array iterieren, wobei Window_end die rechte Grenze des Fensters ist. für window_end im Bereich (len (arr)): # Fügen Sie das aktuelle Element dem window_sum hinzu. window_sum = arr [window_end] # Während die Summe des aktuellen Fensters größer oder gleich s: während window_sum> = s: # Berechnen Sie die aktuelle Fenstergröße und aktualisieren Sie min_length, falls kleiner. min_length = min (min_length, window_end - window_start 1) # Verkleinern Sie das Fenster von links, indem Sie das Element am window_start entfernen. window_sum -= arr [window_start] # Bewegen Sie den Beginn des Fensters nach rechts. window_start = 1 # Wenn min_length aktualisiert wurde, geben Sie es zurück. Ansonsten return 0 (dh kein gültiges Subtarray wurde gefunden). return min_length wenn min_length! = float ('inf') else 0

Erläuterung

:

Das Fenster erweitert durch Erhöhen von window_end, bis die Summe überschreitet oder gleich s.
Sobald die Bedingung erfüllt ist, beginnt das Fenster von links (window_start), um die minimale Subtarray -Größe zu finden.
Dieser Ansatz ist effizient, da er das Problem von o (n^2) auf o (n) reduziert, indem sie Wiedererzusagen vermieden.

.

---

Schritte zur Implementierung von Schiebungsfensterlösungen

1. Definieren Sie die Fenstergrenzen
: Sie müssen den Start und das Ende des Fensters definieren.

2. Setzen Sie eine Anfangsbedingung
: Für feste Fenster initialisieren Sie die Summe/Produkt/Bedingung für das erste Fenster. Für dynamische Fenster hängt die Anfangsbedingung vom Ziel des Problems ab.

3. schieben Sie das Fenster
   :
   • Für feste Fenstergröße: Schalten Sie das Fenster durch Hinzufügen des nächsten Elements und Entfernen des Elements, das sich nicht mehr im Fenster befindet.
   Für dynamische Fenster: Erweitern oder vertrag das Fenster basierend auf der Bedingung, die Sie befriedigen möchten.

4. prüfen und aktualisieren Ergebnisse
: Nach jeder Fensterbewegung aktualisieren Sie das Ergebnis (z. B. maximale Summe, Mindestlänge usw.).

---

Gemeinsame Interviewfragen unter Verwendung von Schiebernfenster

1. längste Substring, ohne Zeichen zu wiederholen
   problem
   • : Finden Sie die Länge des längsten Substrings, ohne Zeichen zu wiederholen.
   muster
   : Verwenden Sie ein dynamisches Schiebfenster, um zu erweitern, bis ein doppelter Zeichen gefunden wird, und dann das Fenster zu verschließen, bis die Bedingung erfüllt ist.

2. Maximale Summe Subtarray der Größe k
   problem
   • : Bei einer Reihe von ganzen Zahlen und einer Ganzzahl k die maximale Summe einer Teilestalroberin der Größe k. finden
   muster
   : Verwenden Sie ein Schiebefenster mit fester Größe, um die Summe der k -Elemente beizubehalten und die maximale Summe zu aktualisieren, während Sie das Fenster über das Array schieben.

3. Kleinstes Subtarray mit einer gegebenen Summe
   problem
   • : Finden Sie die Länge der kleinsten zusammenhängenden Subtarray, deren Summe größer oder gleich s. .
   muster
   : Verwenden Sie ein dynamisches Gleitfenster, das sich ausdehnt, um ein gültiges Subtarray und Verträge zu finden, um seine Länge zu minimieren.

---

Schiebefenster -Hacks für Interviews

1. denken Sie in den Fenstergrenzen
: Beginnen Sie mit dem Nachdenken darüber, wo das Fenster starten und enden soll. Dies hilft Ihnen, den genauen Bereich zu identifizieren, mit dem Sie arbeiten.

2. Verwenden Sie einen HashMap oder einsatz für dynamische Windows
: Wenn Sie sich mit Substrings oder einzigartigen Elementen befassen, verwenden Sie eine Set, um die Elemente im Fenster zu verfolgen.

3. ]

   Beginnen Sie mit Brute-Force und optimieren Sie dann
: In einigen Problemen kann es Ihnen helfen, mit einem Brute-Force-Ansatz (z.

4. suchen nach optimalen Bedingungen : Wenn das Problem eine Optimierungskomponente hat (z.

Abschluss

---

Das Schiebenfenstermuster ist ein leistungsstarkes Werkzeug zur Lösung vieler Codierungsinterviewprobleme, insbesondere solche, an denen Sequenzen wie Arrays oder Zeichenfolgen beteiligt sind. Durch das Beherrschen von festem und dynamischen Schiebernfenstern können Sie eine Vielzahl von Problemen effizienter angehen.

Im nächsten Artikel werden wir die

zwei Zeigertechniken

untersuchen, eine weitere hochwirksame Strategie, die den Ansatz des Schiebungsfensters in Problemen, die Paare oder Vergleiche zwischen Elementen beinhalten, häufig ergänzt. Bleib dran für Teil 3!