Méthode des deux pointeurs

2.1 Définition de la méthode des deux pointeurs.

Méthode des deux pointeurs — c'est une technique utilisée pour résoudre diverses tâches sur les tableaux et les chaînes, en utilisant deux pointeurs (indices) qui se déplacent sur les données selon des règles spécifiques. Cette méthode permet de résoudre efficacement des tâches liées à la recherche de paires d'éléments, de sous-ensembles qui satisfont des conditions données.

Cette méthode suppose l'utilisation de deux pointeurs, qui sont généralement initialisés aux extrémités opposées de la structure de données et se déplacent l'un vers l'autre ou selon une règle spécifiée. La méthode des deux pointeurs peut réduire considérablement la complexité temporelle de l'algorithme par rapport à des approches plus naïves.

Principes de base

1. Initialisation des deux pointeurs: Les pointeurs peuvent être positionnés au début et à la fin d'un tableau ou d'une chaîne, ou à différents indices selon la tâche.
2. Déplacement des pointeurs: Les pointeurs se déplacent selon une règle spécifique (par exemple, les deux pointeurs se dirigent vers le centre, ou un pointeur avance pendant que l'autre reste en place).
3. Vérification de la condition: À chaque étape, la condition est vérifiée, ce qui détermine le déplacement ultérieur des pointeurs ou l'arrêt de l'algorithme.

Complexité temporelle :

O(n) — dans la plupart des cas, car les deux pointeurs parcourent le tableau une ou plusieurs fois, mais pas plus de O(n) itérations au total.

Pour certaines tâches, en fonction des conditions et des positions initiales des pointeurs, la complexité temporelle peut être de O(n log n) ou de O(n^2), mais cela reste rare.

Exemples de tâches résolues par la méthode des deux pointeurs :

2.2 Recherche de deux nombres dans un tableau dont la somme est un nombre donné.

Tâche :

Trouver deux nombres dans un tableau trié dont la somme est égale à un nombre donné target.

Solution :

On initialise un pointeur au début du tableau, l'autre à la fin. On vérifie la somme des éléments sous les pointeurs :

• Si la somme est égale à target, on renvoie les indices.
• Si la somme est inférieure à target, on déplace le pointeur de gauche vers la droite.
• Si la somme est supérieure à target, on déplace le pointeur de droite vers la gauche.

Complexité temporelle : O(n).

Exemple de code en Python :

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Vérification d'un palindrome

Tâche :

Vérifier si une chaîne est un palindrome.

Solution :

On initialise les pointeurs au début et à la fin de la chaîne. On compare les caractères sous les pointeurs :

• Si les caractères sont égaux, on déplace les deux pointeurs l'un vers l'autre.
• Si les caractères ne sont pas égaux, la chaîne n'est pas un palindrome.

Complexité temporelle : O(n).

Exemple de code en Python :

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Suppression des doublons dans un tableau trié

Tâche :

Supprimer les doublons d'un tableau trié.

Solution :

On utilise deux pointeurs, un pour la position actuelle dans le tableau résultant, l'autre pour parcourir tous les éléments :

• Si l'élément actuel n'est pas égal au précédent, on l'écrit dans le tableau résultant.

Complexité temporelle : O(n).

Exemple de code en Python :

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index