Résoudre ‘Two Sum II’ en Python – Question d’Entretien avec Tableau Trié

Introduction

Dans cet article, nous allons explorer la solution au problème ‘Two Sum II’, une question courante dans les entretiens techniques de programmation. Ce problème est une variante du classique ‘Two Sum’, mais se différencie par le fait que le tableau d’entiers est déjà trié. Comprendre et résoudre ce type de problème est crucial pour les entretiens, car il teste votre capacité à capitaliser sur les propriétés des structures de données.

L’objectif de cet article est de décrire une méthode efficace pour résoudre le problème en utilisant une approche appelée ‘Deux Pointeurs’. Nous expliquerons chaque étape en détail et mettrons en œuvre la solution en Python.

Comprendre le Problème

Énoncé du problème

Nous avons un tableau d’entiers trié dans l’ordre croissant et nous devons identifier deux entiers dont la somme correspond à une cible donnée. Les contraintes incluent le fait que chaque entrée a exactement une solution et que nous ne pouvons pas utiliser la même élément deux fois.

Exemples pratiques

Exemple 1

• Entrée : nums = [2, 7, 11, 15], target = 9
• Sortie : [1, 2]
• Les indices de l’élément 2 et 7 (base 1) s’additionnent pour donner 9.

Exemple 2

• Entrée : nums = [2, 3, 4], target = 6
• Sortie : [1, 3]
• Les indices de l’élément 2 et 4 (base 1) s’additionnent pour donner 6.

Analyse de la Complexité

Approche Naïve vs Optimisée

Une approche de force brute pourrait consister à parcourir toutes les paires dans le tableau et vérifier leur somme, ce qui résulterait en une complexité de O(n^2). Cependant, cette méthode est inefficace pour les grands ensembles de données.

Importance du tableau trié

L’avantage d’un tableau trié est que nous pouvons utiliser cette propriété pour concevoir une solution efficace, ce qui nous amène à l’algorithme optimisé utilisant ‘Deux Pointeurs’.

Algorithme Optimisé : Utilisation de l’approche ‘Deux Pointeurs’

Présentation du concept de ‘Deux Pointeurs’

L’idée derrière l’approche des ‘Deux Pointeurs’ est d’utiliser deux indices pour représenter une paire potentielle. Initialement, l’un des pointeurs est placé au début du tableau et l’autre à la fin.

Étapes détaillées de l’algorithme

1. Initialisation : Pointeur gauche au début (index 0) et pointeur droit à la fin (index len(nums) – 1) du tableau.
2. Boucle : Tant que le pointeur gauche est inférieur au pointeur droit :
3. Calculez la somme des nombres pointés.
4. Si la somme est égale à la cible, retournez les indices (en ajustant pour une base de 1).
5. Si la somme est inférieure à la cible, déplacez le pointeur gauche vers la droite.
6. Si la somme est supérieure à la cible, déplacez le pointeur droit vers la gauche.
7. Complexité : Cette méthode assure une complexité de O(n) en raison du parcours unique du tableau.

Implémentation en Python

Voici comment vous pouvez implémenter cet algorithme en Python :

def two_sum_ii(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            return [left + 1, right + 1]  # indices 1-based

        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

# Exemple d'utilisation
print(two_sum_ii([2, 7, 11, 15], 9))  # Sortie : [1, 2]

Tests et Validation

Importance des tests unitaires

Il est essentiel de s’assurer que votre fonction traite correctement différentes situations. Les tests vous permettent de vérifier la robustesse et la précision de votre code.

Conception de cas de test

1. Cas de base : two_sum_ii([2, 7, 11, 15], 9) devrait retourner [1, 2].
2. Cas limites : Essayez des tableaux comme [1, 2] avec cible 3.
3. Cas sans solution : Comme chaque entrée a précisément une solution, un tel cas n’est pas applicable ici.

En utilisant assert, nous pouvons valider facilement ces cas :

assert two_sum_ii([2, 7, 11, 15], 9) == [1, 2]
assert two_sum_ii([2, 3, 4], 6) == [1, 3]
assert two_sum_ii([-1, 0], -1) == [1, 2]

Discussion sur les Variantes

Adaptations possibles

Pour certaines variantes du problème, comme lorsque le tableau n’est pas trié, une autre méthode, comme l’utilisation d’un dictionnaire, pourrait être plus appropriée.

Analyse de complexité

Pour des structures de données différentes ou des contraintes modifiées, il est crucial de réévaluer constamment la complexité pour garantir l’efficacité.

Meilleures Pratiques en Python

• Codage lisible : Utilisez des noms de variables explicites et des commentaires au besoin.
• Techniques de débogage : Intégrez print() pour inspecter les variables ou utilisez des outils comme pdb.

Conclusion

Nous avons couvert le problème ‘Two Sum II’ et mis en œuvre une approche efficace à l’aide de pointeurs. Comprendre ces solutions vous aide à renforcer votre utilisation des structures de données et algorithmes de base, qui sont des compétences essentielles pour réussir dans les entretiens techniques. Continuez à pratiquer avec des problèmes similaires pour améliorer vos compétences.

Ressources Supplémentaires

• LeetCode pour la pratique des algorithmes.
• Livres recommandés : « Introduction to Algorithms » de Cormen et al. pour des bases solides.
• Geeks for Geeks pour des articles connexes et plus détaillés.