Two Pointers et Sliding Window : optimisation pour tableaux

1. Présentation générale

Quand vous rencontrez un problème de parcours de tableau ou de chaîne où la solution brute-force s’exécute en O(n²) ou O(n³), les deux techniques two pointers et sliding window vous aideront généralement à réduire la complexité à O(n). Cet article explique l’idée centrale de chaque technique, accompagnée d’exemples Java concrets : two sum sur un tableau trié, vérification de palindrome, somme maximale d’une sous-suite dans une fenêtre fixe, et plus longue sous-chaîne sans caractère répétitif. Après la lecture, vous reconnaîtrez le motif et pourrez l’appliquer à de nombreux problèmes similaires.

2. Two Pointers : qu’est-ce que c’est

Two pointers est une technique utilisant deux variables d’index (pointeurs) se déplaçant sur une structure de données (généralement un tableau ou une chaîne triée) pour éviter les parcours imbriqués. Les deux pointeurs peuvent se déplacer :

• Même direction (fast/slow) : utilisée pour supprimer les éléments en double, détecter les cycles.
• Directions opposées (left/right des deux extrémités) : utilisée pour trouver une paire de somme égale à la cible, vérifier un palindrome.

2.1. Two pointers en directions opposées : trouver une paire dont la somme égale la cible

Problème classique : étant donné un tableau trié en ordre croissant, trouver deux nombres dont la somme égale la cible.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

Explication :

• left commence au début du tableau, right à la fin du tableau.
• Si sum < target, le nombre à left est trop petit, donc on augmente left pour obtenir un nombre plus grand.
• Si sum > target, le nombre à right est trop grand, donc on diminue right.
• La boucle s’exécute en maximum n étapes car à chaque itération left ou right se déplace d’un cran, donnant une complexité O(n) au lieu de O(n²) avec une approche à deux boucles imbriquées.

Test avec JUnit 5 + AssertJ :

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Remarque : cette technique nécessite un tableau déjà trié. Si le tableau n’est pas trié, vous devez d’abord le trier (O(n log n)) ou utiliser HashMap pour maintenir O(n) sans tri.

2.2. Two pointers pour vérifier un palindrome

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Les deux pointeurs partent des deux extrémités de la chaîne, comparent les caractères puis avancent vers le milieu. S’ils rencontrent une paire de caractères différents, ils renvoient false immédiatement — pas besoin de parcourir tout. C’est pourquoi cette technique est plus rapide qu’inverser la chaîne puis comparer (reverse().equals()), car elle évite de créer un objet StringBuilder intermédiaire.

3. Qu’est-ce que le Sliding Window ?

Le sliding window est une variante de two pointers, applicable aux problèmes concernant les sous-séquences contiguës (subarray/substring). Au lieu de recalculer à partir du début pour chaque position de départ, vous maintenez une « fenêtre » [left, right] et la mettez à jour progressivement au fur et à mesure que la fenêtre glisse, en réutilisant les résultats précédemment calculés.

Il y a deux types :

• Fixed-size window : la taille de la fenêtre est fixe (par exemple k éléments).
• Variable-size window : la taille s’adapte selon la condition du problème.

3.1. Fixed-size window : plus grande somme de sous-suite de taille k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Explication :

• La première boucle calcule la somme de la première fenêtre (de l’index 0 à windowSize - 1).
• À partir de là, chaque fois que vous décalez la fenêtre d’un pas vers la droite : vous ajoutez le nouvel élément (numbers[right]) et soustrayez l’élément qui quitte la fenêtre (numbers[right - windowSize]).
• Ainsi, chaque étape ne coûte que O(1) au lieu de recalculer la somme en O(k), pour une complexité totale O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // fenêtre [5, 1, 3]
    }
}

3.2. Variable-size window : plus longue sous-chaîne sans caractère répétitif

Dans ce problème, la fenêtre s’adapte selon la condition « pas de caractère répétitif ».

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Explication :

• right avance toujours (élargit la fenêtre), left saute seulement quand on rencontre un caractère répétitif à l’intérieur de la fenêtre actuelle.
• lastSeenIndex enregistre la position d’apparition la plus récente de chaque caractère pour savoir où left doit sauter.
• La condition lastSeenIndex.get(current) >= left garantit qu’on considère un caractère comme « répétitif » seulement s’il se trouve toujours à l’intérieur de la fenêtre actuelle, évitant que left ne recule incorrectement.
• Chaque caractère est traité exactement une fois lors du déplacement de right, donc la complexité totale est O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Sortie lors du débogage manuel avec "abcabcbb" :

right=0 'a' -> fenêtre="a"    longueur=1
right=1 'b' -> fenêtre="ab"   longueur=2
right=2 'c' -> fenêtre="abc"  longueur=3
right=3 'a' -> répétitif, left=1 -> fenêtre="bca" longueur=3
right=4 'b' -> répétitif, left=2 -> fenêtre="cab" longueur=3
...
maxLength = 3

4. Comparaison et quand utiliser quelle technique

Situation	Technique appropriée
Tableau trié, trouver une paire/triplet satisfaisant une condition de somme	Two pointers en directions opposées
Vérifier la symétrie (palindrome), inverser un tableau sur place	Two pointers en directions opposées
Supprimer les éléments en double dans un tableau trié	Two pointers même direction (fast/slow)
Subarray/substring de taille fixe k	Sliding window fixed-size
Subarray/substring satisfaisant une condition dynamique (pas de répétition, somme ≤ cible…)	Sliding window variable-size

Point commun : les deux techniques évitent les recalculs sur les parties déjà traitées, en passant de O(n²) à O(n) en maintenant l’état (sum, set, map) lors du déplacement des pointeurs/fenêtres.

5. Erreurs courantes

• Oublier la condition d’arrêt left < right : cela peut facilement causer une boucle infinie ou comparer un élément avec lui-même quand left == right.
• Appliquer two pointers à un tableau non trié en oubliant de le trier d’abord — le résultat sera complètement incorrect car la logique d’augmentation/diminution des pointeurs repose sur la monotonie du tableau.
• Dans le sliding window, oublier de mettre à jour l’état quand left se déplace : par exemple, oublier de supprimer l’ancien élément de HashMap/sum, ce qui fait que la fenêtre « se souvient » de données n’appartenant plus à la fenêtre.
• Confondre la condition d’élargissement/rétrécissement de la fenêtre : avec variable-size window, vous devez clairement définir quelle condition fait avancer right et quelle condition fait avancer left — si c’est inversé, la fenêtre ne se rétrécira jamais correctement.

Remarque : ces deux techniques ne conviennent pas quand le problème demande d’examiner toutes les combinaisons de sous-ensembles non contigus (par exemple subset sum) — dans ce cas, vous avez besoin du backtracking ou de la programmation dynamique, pas du sliding window.

6. Conclusion

Two pointers et sliding window sont deux outils fondamentaux pour résoudre les problèmes de tableaux/chaînes avec une complexité linéaire. Reconnaître le motif — un tableau trié où il faut trouver une paire, ou des subarray/substring contigus à optimiser — vous aide à choisir la bonne technique et à écrire du code concis et facile à tester comme les exemples ci-dessus. Pendant l’entraînement, essayez de redessiner l’état de left/right à chaque étape pour bien comprendre l’invariant avant de coder.