Comment implémenter la fenêtre glissante en Python

Une fenêtre glissante conserve une plage contiguë d’éléments et la déplace dans une liste ou une chaîne. En Python, cette technique est utile lorsque l’on peut mettre à jour chaque résultat à partir de la fenêtre précédente, au lieu de recalculer tous ses éléments. Les exemples ci-dessous présentent trois formes courantes : une fenêtre de taille fixe, une fenêtre variable sans caractères répétés et une fenêtre répondant à une somme cible.

Qu’est-ce que la technique de la fenêtre glissante ?

Une fenêtre est une plage délimitée par une position gauche et une position droite. Sa longueur peut être fixe ou varier au fil des ajouts et des retraits effectués par l’algorithme. Comme ses éléments restent contigus, la fenêtre glissante convient aux problèmes portant sur des sous-tableaux et des sous-chaînes ; elle ne décrit pas directement des sélections arbitraires comportant des éléments omis.

Cette technique permet souvent d’éviter des calculs répétés. Par exemple, après avoir calculé la somme d’une fenêtre, la décaler d’une position consiste à soustraire la valeur qui en sort et à ajouter celle qui y entre. Cette mise à jour prend un temps constant. La complexité totale dépend de l’algorithme utilisé et de sa structure de données : la fenêtre glissante ne garantit donc ni une accélération ni un temps en O(n) pour tous les problèmes.

Implémenter une fenêtre glissante pour trouver la somme maximale d’un sous-tableau de taille K

Pour une liste de nombres et une taille de fenêtre positive k, commencez par additionner les k premières valeurs. Faites ensuite avancer la fenêtre d’une position à la fois, en mettant à jour sa somme avec les valeurs qui sortent et qui entrent. Conservez la somme maximale rencontrée. Cet exemple renvoie None si k n’est pas positif ou dépasse la longueur de la liste, ce qui précise le contrat d’entrée.

Avec la liste [2, 1, 5, 1, 3, 2] et k = 3, les fenêtres sont [2, 1, 5], [1, 5, 1], [5, 1, 3] et [1, 3, 2]. Le programme affiche la somme la plus élevée. Il s’exécute en O(n) et utilise O(1) espace supplémentaire, où n désigne la longueur de la liste.

def max_sum_subarray(values, k):
    if k <= 0 or k > len(values):
        return None

    window_sum = sum(values[:k])
    best_sum = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum

values = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(values, k))

Cet exemple de code est fourni pour que vous puissiez l’exécuter ; aucun résultat d’exécution n’est annoncé ici.

Fenêtre glissante pour trouver la plus longue sous-chaîne sans répétition de caractères

Dans ce problème, la fenêtre ne contient aucun caractère en double. Parcourez la chaîne avec la position droite et ajoutez chaque nouveau caractère à un ensemble. Si le caractère est déjà présent, avancez la position gauche et retirez les caractères qui quittent la fenêtre jusqu’à ce que le doublon disparaisse. Une fois cette condition rétablie, mettez à jour la longueur maximale.

Chaque position avance au plus une fois, et chaque caractère entre dans l’ensemble puis en sort au plus une fois. Pour une chaîne de longueur n, l’algorithme s’exécute donc en O(n) et utilise O(min(n, taille de l’alphabet)) espace. Python parcourt les points de code Unicode ; un graphème perçu comme un seul caractère, par exemple une lettre de base combinée à un signe, peut en contenir plusieurs.

def longest_unique_substring_length(text):
    window_chars = set()
    left = 0
    best_length = 0

    for right, char in enumerate(text):
        while char in window_chars:
            window_chars.remove(text[left])
            left += 1
        window_chars.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

text = "abcabcbb"
print(longest_unique_substring_length(text))

Cet exemple de code est fourni pour que vous puissiez l’exécuter ; aucun résultat d’exécution n’est annoncé ici.

Fenêtre glissante pour trouver la somme minimale d’un sous-tableau de taille donnée

Pour une somme cible, cette méthode trouve le sous-tableau contigu le plus court dont la somme est supérieure ou égale à cette cible. Elle suppose que toutes les valeurs sont non négatives : lorsque la somme courante atteint la cible, retirer une valeur à gauche ne peut pas l’augmenter ; réduire la fenêtre permet donc de chercher une plage valide plus courte. Avec des valeurs négatives, ce raisonnement ne tient plus et il faut utiliser un autre algorithme.

La fonction renvoie 0 si aucun sous-tableau ne satisfait la condition. Avec des valeurs non négatives et une cible positive, chaque position est ajoutée puis retirée au plus une fois ; le temps d’exécution est donc O(n) et l’espace supplémentaire O(1). Le code accepte une cible nulle ou négative et renvoie alors une longueur nulle, puisqu’aucun élément n’est nécessaire pour l’atteindre.

def min_subarray_length(target, values):
    if target <= 0:
        return 0

    left = 0
    running_sum = 0
    shortest = len(values) + 1

    for right, value in enumerate(values):
        running_sum += value
        while running_sum >= target:
            shortest = min(shortest, right - left + 1)
            running_sum -= values[left]
            left += 1

    return 0 if shortest > len(values) else shortest

values = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_length(target, values))

Cet exemple de code est fourni pour que vous puissiez l’exécuter ; aucun résultat d’exécution n’est annoncé ici.

Conclusion

La fenêtre glissante est une méthode utile pour raisonner sur des plages contiguës dans une liste ou une chaîne. Choisissez une fenêtre fixe lorsque sa taille est connue ; ajustez ses limites lorsqu’une condition, comme l’absence de caractères répétés ou une somme cible, détermine la plage. Avant d’utiliser cette technique, vérifiez que l’état conservé peut être mis à jour à mesure que la fenêtre avance et que les hypothèses de l’algorithme correspondent aux données. Ces exemples couvrent des problèmes courants d’entretien Python, mais d’autres contraintes peuvent nécessiter une approche différente.

FAQ

1. Quand utiliser une fenêtre glissante ? Utilisez-la lorsqu’un problème porte sur des sous-tableaux ou des sous-chaînes contigus et que le résultat courant peut être mis à jour en déplaçant l’une ou les deux limites.
2. Tous les algorithmes à fenêtre glissante sont-ils en O(n) ? Non. Ces exemples sont linéaires parce que le déplacement des limites et les mises à jour effectuées à chaque étape sont bornés. D’autres algorithmes peuvent effectuer davantage de travail à chaque déplacement.
3. Puis-je utiliser cette fenêtre de somme minimale avec des nombres négatifs ? Pas telle qu’elle est écrite. Sa règle de réduction repose sur des valeurs non négatives ; retirer un élément négatif peut faire augmenter la somme.
4. Quelle est la différence entre un sous-tableau et une sous-séquence ? Un sous-tableau est contigu. Une sous-séquence peut omettre des positions tout en conservant l’ordre ; une fenêtre ne parcourt donc pas toutes les sous-séquences.