Méthode de la fenêtre glissante

3.1 Définition de la méthode de la fenêtre glissante.

La méthode de la fenêtre glissante (Sliding Window) est une technique utilisée pour résoudre des problèmes sur les tableaux ou les chaînes, dans laquelle un sous-tableau (ou sous-chaîne) fixe est déplacé sur les données afin de rechercher une solution optimale. Cela permet de traiter les éléments dans une fenêtre de taille fixe et de modifier dynamiquement la fenêtre en fonction des conditions du problème.

Cette technique est particulièrement utile pour les problèmes liés aux séquences de données, comme les tableaux ou les chaînes, et aide à réduire la complexité temporelle par rapport à des approches plus naïves.

Principes de base

• Initialisation de la fenêtre: Fixez le début et la fin de la fenêtre aux positions initiales.
• Déplacement de la fenêtre: Déplacez les limites de la fenêtre séquentiellement, en ajoutant des éléments d'un côté et en supprimant des éléments de l'autre.
• Traitement de la fenêtre: À chaque étape, effectuez les calculs nécessaires pour la fenêtre actuelle.

Complexité temporelle et spatiale de la méthode de la fenêtre glissante

Complexité temporelle :

• O(n) — dans la plupart des cas, car le pointeur ou la fenêtre se déplace de manière linéaire à travers le tableau, en vérifiant chaque position possible de la fenêtre.

Complexité spatiale :

• O(1) — si une quantité fixe de mémoire supplémentaire est utilisée pour stocker les valeurs actuelles.
• O(k) — si les éléments doivent être stockés à l'intérieur de la fenêtre actuelle de taille k.

3.2 Trouver la somme maximale d'un sous-tableau.

Trouver la somme maximale d'un sous-tableau de taille fixe

Problème :

Trouver un sous-tableau de taille fixe k avec la somme maximale.

Solution :

Utilisez la méthode de la fenêtre glissante pour maintenir la somme courante du sous-tableau et mettez à jour la somme maximale au fur et à mesure du déplacement de la fenêtre.

Complexité temporelle : O(n).

Exemple de code en 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 Trouver toutes les anagrammes de la sous-chaîne dans une chaîne

Problème :

Trouver toutes les anagrammes d'une sous-chaîne donnée p dans une chaîne s.

Solution :

Utilisez la méthode de la fenêtre glissante pour maintenir un dictionnaire de fréquence des caractères de la fenêtre actuelle et comparez-le avec le dictionnaire de fréquence de la sous-chaîne.

Complexité temporelle : O(n).

Exemple de code en 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 Trouver le sous-tableau minimal

Trouver le sous-tableau minimal avec une somme dépassant une valeur donnée

Problème :

Trouver un sous-tableau minimal avec une somme d'éléments dépassant une valeur donnée S.

Solution :

Utilisez la méthode de la fenêtre glissante pour étendre la limite droite jusqu'à ce que la somme dépasse S, puis déplacez la limite gauche pour minimiser la longueur du sous-tableau.

Complexité temporelle : O(n).

Exemple de code en 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