Sliding-Window-Methode

3.1 Definition der Sliding-Window-Methode.

Die Sliding-Window-Methode ist eine Technik, die verwendet wird, um Probleme mit Arrays oder Strings zu lösen, bei denen ein fester Teilbereich (oder Substring) verschoben wird, um eine optimale Lösung zu finden. Dadurch können Elemente in einem Fenster fester Größe verarbeitet und das Fenster je nach Bedingungen der Aufgabe dynamisch geändert werden.

Diese Technik ist besonders nützlich für Aufgaben, die mit Datenfolgen wie Arrays oder Strings zu tun haben, und hilft, die Zeitkomplexität im Vergleich zu naiveren Ansätzen zu reduzieren.

Grundprinzipien

• Initialisierung des Fensters: Setze Anfang und Ende des Fensters auf die Startpositionen.
• Verschiebung des Fensters: Bewege die Grenzen des Fensters nacheinander, füge Elemente von einer Seite hinzu und entferne Elemente von der anderen.
• Verarbeitung des Fensters: Führe bei jedem Schritt die notwendigen Berechnungen für das aktuelle Fenster durch.

Zeit- und Platzkomplexität der Sliding-Window-Methode

Zeitkomplexität:

• O(n) — in den meisten Fällen, da der Zeiger oder das Fenster linear über das Array bewegt wird und jede mögliche Fensterposition überprüft.

Platzkomplexität:

• O(1) — wenn eine feste Menge zusätzlicher Speicher für die Speicherung der aktuellen Werte verwendet wird.
• O(k) — wenn die Elemente innerhalb des aktuellen Fensters der Größe k gespeichert werden müssen.

3.2 Finden der maximalen Summe des Teilarrays.

Finden der maximalen Summe eines Teilarrays fester Größe

Aufgabe:

Finde das Teilarray fester Größe k mit der maximalen Summe.

Lösung:

Wir verwenden die Sliding-Window-Methode, um die aktuelle Summe des Teilarrays beizubehalten und die maximale Summe beim Verschieben des Fensters zu aktualisieren.

Zeitkomplexität: O(n).

Beispielcode in Python:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Finden aller Anagramme eines Substrings in einem String

Aufgabe:

Finde alle Anagramme des gegebenen Substrings p in dem String s.

Lösung:

Wir verwenden die Sliding-Window-Methode, um ein Frequenzwörterbuch der Zeichen des aktuellen Fensters zu führen und es mit dem Frequenzwörterbuch des Substrings zu vergleichen.

Zeitkomplexität: O(n).

Beispielcode in Python:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Finden des minimalen Teilarrays

Finden des minimalen Teilarrays mit einer Summe, die einen gegebenen Wert überschreitet

Aufgabe:

Finde das minimale Teilarray, dessen Summe der Elemente einen gegebenen Wert S überschreitet.

Lösung:

Wir verwenden die Sliding-Window-Methode, um die rechte Grenze zu erweitern, bis die Summe größer als S ist, und dann die linke Grenze zu verschieben, um die Länge des Teilarrays zu minimieren.

Zeitkomplexität: O(n).

Beispielcode in Python:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len