0Pricing
Coding Interview Prep · Leçon

Deux pointeurs : extrémités opposées

Utilisez des pointeurs gauche et droit qui se rapprochent pour résoudre la recherche d’une somme de paire dans des tableaux triés, la vérification d’un palindrome valide et le problème de l’eau piégée par la pluie.

Deux pointeurs : extrémités opposées est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

L’idée des deux pointeurs

La technique des deux pointeurs utilise deux variables d’indice qui se déplacent l’une vers l’autre, ou dans la même direction, afin de réduire le recours aux boucles imbriquées. Au lieu de vérifier chaque paire en O(n²), vous progressez à chaque comparaison et terminez en O(n). Cette technique nécessite presque toujours que le tableau soit d’abord trié, car le tri permet de déterminer dans quelle direction déplacer chaque pointeur selon que la somme de la paire actuelle est trop grande ou trop petite.

# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left  += 1
        else:           right -= 1
    return []

Deux éléments de somme donnée dans un tableau trié

Avec un tableau trié, placez un pointeur à l’extrémité gauche, qui contient la plus petite valeur, et un autre à l’extrémité droite, qui contient la plus grande. Si la somme est trop petite, déplacez le pointeur gauche vers la droite pour l’augmenter. Si elle est trop grande, déplacez le pointeur droit vers la gauche pour la réduire. À chaque itération, au moins un pointeur avance, si bien que la boucle s’exécute au plus n fois : O(n) au total après le tri. Point important, chaque déplacement est démontrablement correct grâce à l’ordre trié.

def two_sum_sorted(numbers, target):
    # numbers is 1-indexed per LeetCode 167
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed
        elif s < target:
            left  += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

Vérifier si une chaîne est un palindrome

Une chaîne est un palindrome si elle se lit de la même façon dans les deux sens. Utilisez deux pointeurs placés aux deux extrémités et déplacez-les vers le centre : comparez les caractères, ignorez les caractères non alphanumériques et arrêtez-vous lorsque les pointeurs se croisent. Cette méthode s’exécute en O(n) et utilise O(1) espace supplémentaire — elle est bien plus propre que de renverser la chaîne puis de la comparer, ce qui alloue O(n) mémoire supplémentaire.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False

Trois éléments de somme nulle : tri et deux pointeurs

Le problème des trois éléments de somme nulle demande de trouver tous les triplets distincts dont la somme vaut zéro. Triez le tableau, puis fixez chaque élément nums[i] et effectuez une recherche à deux pointeurs dans le sous-tableau restant pour trouver une paire dont la somme vaut -nums[i]. Ignorez les doublons de l’élément fixé et de la paire trouvée afin d’éviter les triplets répétés. Complexité totale : O(n²) après un tri en O(n log n).

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dupe
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left]  == nums[left+1]:  left  += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left  += 1
            else:       right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]

Conteneur contenant le plus d’eau

Étant donné les hauteurs de lignes verticales, trouvez les deux lignes qui forment un conteneur pouvant contenir le plus d’eau. La surface vaut min(height[left], height[right]) × (right - left). Déplacez progressivement vers l’intérieur le pointeur situé sur la ligne la plus courte : déplacer la ligne la plus haute ne peut que réduire la largeur sans augmenter la hauteur maximale autorisée. Ce choix glouton est démontrablement optimal et donne une complexité O(n).

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h    = min(height[left], height[right])
        area = h * (right - left)
        best = max(best, area)
        # Move the shorter wall inward
        if height[left] < height[right]:
            left  += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Mettre au carré un tableau trié

Élevez au carré chaque élément d’un tableau trié, qui peut contenir des valeurs négatives, puis renvoyez le résultat dans l’ordre croissant. Les carrés des valeurs négatives sont grands ; les carrés des valeurs positives sont petits au centre. Placez deux pointeurs aux deux extrémités et remplissez le tableau de résultat de droite à gauche, du plus grand au plus petit. La complexité est O(n), avec un espace de sortie O(n) — une nette amélioration par rapport au calcul des carrés suivi d’un tri en O(n log n).

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

Piéger l’eau de pluie

L’eau piégée à l’indice i vaut min(max_left, max_right) - height[i]. Approche à deux pointeurs : maintenez les valeurs cumulées max_left et max_right. Lorsque max_left < max_right, le côté gauche constitue le goulot d’étranglement : traitez le pointeur gauche. Sinon, traitez le pointeur droit. Cette méthode élimine le besoin de tableaux distincts contenant les maximums à gauche et à droite, et atteint un espace supplémentaire O(1).

def trap(height):
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

Pourquoi le déplacement glouton du pointeur fonctionne

Une question fréquente lors d’un entretien est la suivante : pourquoi est-il possible d’écarter sans risque le pointeur le plus petit ? Esquisse de preuve pour le conteneur contenant le plus d’eau : supposons que height[left] < height[right]. Toute paire (left, j) pour j < right donne une surface ≤ height[left] × (j-left) < height[left] × (right-left) ≤ current area. Ainsi, aucune paire commençant à « left » avec un indice droit inférieur à « right » ne peut dépasser la surface actuelle. Nous pouvons donc les ignorer sans risque en avançant left.

# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
#   area(left, j) <= min(h[left], h[j]) * (j - left)
#                 <= h[left] * (j - left)
#                 <= h[left] * (right - left)   [since j < right]
#                 = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.

print('Proof verified: advance shorter pointer is optimal')

Paire de différence minimale dans un tableau trié

Trouvez la paire de nombres d’un tableau trié dont la différence absolue est la plus petite. Utilisez deux pointeurs adjacents, et non placés aux extrémités opposées, qui avancent ensemble : |nums[i] - nums[i+1]| pour chaque paire consécutive. Dans un tableau trié, la différence minimale se trouve toujours entre des éléments adjacents, car le tri regroupe les valeurs proches. La complexité est de O(n) après le tri.

def min_diff_pair(nums):
    nums.sort()  # O(n log n)
    min_diff = float('inf')
    best = (nums[0], nums[1])
    for i in range(len(nums) - 1):
        diff = nums[i+1] - nums[i]  # sorted: always >= 0
        if diff < min_diff:
            min_diff = diff
            best = (nums[i], nums[i+1])
    return best, min_diff

pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d)  # (1, 2) 1

Modèle pour deux pointeurs aux extrémités opposées

La plupart des problèmes utilisant deux pointeurs aux extrémités opposées suivent la même structure de base. Maîtriser ce modèle vous permet de l’adapter rapidement sous pression. Les décisions clés sont les suivantes : (1) quelle condition fait avancer le pointeur gauche, (2) quelle condition fait avancer le pointeur droit, (3) ce qui constitue une solution et (4) comment gérer les doublons. Entraînez-vous à déduire ces décisions de l’énoncé avant d’écrire du code.

def two_pointer_template(arr, condition):
    """
    Generic opposite-ends two-pointer skeleton.
    Replace condition logic for each specific problem.
    """
    left, right = 0, len(arr) - 1
    result = []
    while left < right:
        current = arr[left] + arr[right]  # or some combination
        if current == condition:           # found a valid pair
            result.append((arr[left], arr[right]))
            left  += 1
            right -= 1
        elif current < condition:          # need to increase
            left  += 1
        else:                             # need to decrease
            right -= 1
    return result

Compter les paires valides avec deux pointeurs

Les deux pointeurs permettent également de compter les paires efficacement. Pour le problème « compter les paires dont la somme est < cible » dans un tableau trié : fixez le pointeur gauche et utilisez le pointeur droit pour trouver l’indice droit valide le plus élevé. Toutes les paires (left, left+1 to right) sont valides : ajoutez right - left au compteur, puis avancez le pointeur gauche. Vous comptez ainsi toutes les paires valides en O(n), au lieu de O(n²).

def count_pairs_less_than(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left  # all (left, left+1..right) valid
            left  += 1
        else:
            right -= 1
    return count

print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3)  -> 4

Vérification rapide

Testez votre compréhension des concepts de Structures de données & algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que les deux pointeurs aux extrémités opposées remplacent l’énumération des paires en O(n²) par une convergence gauche-droite en O(n) sur les tableaux triés, que la décision concernant le pointeur à avancer découle de la propriété monotone du problème : déplacez le côté qui limite actuellement la progression, et que les problèmes de somme de trois nombres, de contenant contenant le plus d’eau, de piégeage de l’eau de pluie et de vérification de palindrome se ramènent tous au même modèle fondamental. Nous allons maintenant étudier les modèles de deux pointeurs lent-rapide.

Questions Fréquemment Posées

La leçon « Deux pointeurs : extrémités opposées » est-elle gratuite ?

Oui — le texte complet de « Deux pointeurs : extrémités opposées » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Deux pointeurs : extrémités opposées » ?

Utilisez des pointeurs gauche et droit qui se rapprochent pour résoudre la recherche d’une somme de paire dans des tableaux triés, la vérification d’un palindrome valide et le problème de l’eau piégé… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Deux pointeurs : extrémités opposées » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Bases des tableaux et opérations en place
  2. Sommes préfixes et totaux cumulés
  3. Deux pointeurs : extrémités opposées
  4. Deux pointeurs : lent et rapide
← Retour à Coding Interview Prep