Sliding Window

Vous devez trouver la somme maximale de K éléments consécutifs dans un tableau. L'approche naïve : pour chaque position, additionner les K éléments. Si le tableau a N éléments, ça fait N × K opérations. Avec un tableau de 10 millions d'éléments et K = 1000, c'est 10 milliards d'opérations. Le Sliding Window ramène ça à 10 millions — en une seule passe.

L'approche brute force : le problème

Prenons un exemple concret. Tableau : [2, 1, 5, 1, 3, 2], K = 3. On veut la somme maximale de 3 éléments consécutifs.

Position 0 : 2 + 1 + 5 = 8
Position 1 : 1 + 5 + 1 = 7
Position 2 : 5 + 1 + 3 = 9  ← maximum
Position 3 : 1 + 3 + 2 = 6

À chaque position, on recalcule toute la somme. On additionne K éléments, N-K+1 fois. Complexité : O(N × K).

Le gaspillage est évident : entre la position 0 (2+1+5) et la position 1 (1+5+1), on a recalculé 1+5 alors que ces deux éléments étaient déjà dans la somme précédente.

L'insight : réutiliser le calcul

Au lieu de tout recalculer, on peut mettre à jour la somme en retirant l'élément qui sort de la fenêtre et en ajoutant celui qui entre.

Fenêtre [2, 1, 5] → somme = 8
         ↓
Retire 2, ajoute 1 → somme = 8 - 2 + 1 = 7
Fenêtre [1, 5, 1] → somme = 7
         ↓
Retire 1, ajoute 3 → somme = 7 - 1 + 3 = 9
Fenêtre [5, 1, 3] → somme = 9
         ↓
Retire 5, ajoute 2 → somme = 9 - 5 + 2 = 6
Fenêtre [1, 3, 2] → somme = 6

Chaque déplacement coûte 2 opérations (une soustraction, une addition) au lieu de K. Complexité totale : O(N).

Fenêtre fixe : implémentation

function maxSumSubarray(nums: number[], k: number): number {
  // Calculer la somme de la première fenêtre
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
 
  let maxSum = windowSum;
 
  // Faire glisser la fenêtre
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i];       // Ajouter l'élément qui entre
    windowSum -= nums[i - k];   // Retirer l'élément qui sort
    maxSum = Math.max(maxSum, windowSum);
  }
 
  return maxSum;
}
 
// maxSumSubarray([2, 1, 5, 1, 3, 2], 3) → 9

C'est le cas le plus simple du Sliding Window : la fenêtre a une taille fixe de K éléments, et elle glisse d'une position à chaque itération.

Fenêtre variable : quand la taille change

Le Sliding Window devient encore plus puissant avec une fenêtre de taille variable. La fenêtre s'agrandit ou se réduit selon une condition.

Problème : trouver le plus petit sous-tableau dont la somme est supérieure ou égale à un objectif.

Tableau : [2, 3, 1, 2, 4, 3], objectif = 7
Réponse : 2 (le sous-tableau [4, 3])

function minSubarrayLen(target: number, nums: number[]): number {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;
 
  for (let right = 0; right < nums.length; right++) {
    windowSum += nums[right]; // Agrandir la fenêtre
 
    // Réduire la fenêtre tant que la condition est remplie
    while (windowSum >= target) {
      minLength = Math.min(minLength, right - left + 1);
      windowSum -= nums[left]; // Retirer l'élément de gauche
      left++;
    }
  }
 
  return minLength === Infinity ? 0 : minLength;
}

Le pointeur right avance toujours. Le pointeur left avance quand la fenêtre remplit la condition. Chaque élément est visité au maximum deux fois (une fois par right, une fois par left). Complexité : O(N).

Visualisation de la fenêtre variable

[2, 3, 1, 2, 4, 3]  target = 7
 L
 R           sum=2  < 7 → agrandir

[2, 3, 1, 2, 4, 3]
 L  R        sum=5  < 7 → agrandir

[2, 3, 1, 2, 4, 3]
 L     R     sum=6  < 7 → agrandir

[2, 3, 1, 2, 4, 3]
 L        R  sum=8  >= 7 → min=4, réduire

[2, 3, 1, 2, 4, 3]
    L     R  sum=6  < 7 → agrandir

[2, 3, 1, 2, 4, 3]
    L        R  sum=10 >= 7 → min=4, réduire

[2, 3, 1, 2, 4, 3]
       L     R  sum=7  >= 7 → min=3, réduire

[2, 3, 1, 2, 4, 3]
          L  R  sum=7  >= 7 → min=2 ✓, réduire

[2, 3, 1, 2, 4, 3]
             LR sum=3  < 7 → fin

Résultat : 2

Problèmes classiques en Sliding Window

Reconnaître un problème Sliding Window

Le Sliding Window s'applique quand :

• On travaille sur un tableau ou une chaîne de caractères
• On cherche un sous-ensemble contigu (sous-tableau, sous-chaîne)
• On veut optimiser une propriété sur ce sous-ensemble (somme, longueur, nombre d'éléments uniques)
• L'approche brute force implique deux boucles imbriquées

Les signaux dans l'énoncé : "sous-tableau contigu", "fenêtre de taille K", "plus longue sous-chaîne", "plus court sous-tableau qui satisfait..."

Le Sliding Window est l'une des techniques algorithmiques les plus rentables à maîtriser. Le principe est toujours le même : au lieu de recalculer depuis zéro, mettre à jour le résultat en ajoutant ce qui entre dans la fenêtre et en retirant ce qui en sort. Une idée simple qui transforme un O(N²) en O(N) — et qui revient constamment en entretien technique.