Trouver une paire d’une somme donnée
Faire mieux que la force brute en O(n^2)
Trouver une paire d’une somme donnée est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Le problème de la somme d’une paire
Étant donné un tableau et une cible, trouvez deux valeurs dont la somme atteint cette cible. C’est l’un des exercices d’échauffement les plus courants dans les concours. 🔍
La méthode par force brute
La solution évidente essaie toutes les paires avec deux boucles imbriquées. Elle fonctionne, mais vérifier toutes les paires coûte O(n^2) et peut être beaucoup trop lent.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Quand la force brute échoue
Avec n proche de 100000, O(n^2) représente dix milliards de vérifications et vous subirez un TLE. Les contraintes vous indiquent qu’il faut trouver une méthode plus rapide.
Trier, puis parcourir
Si vous sort d’abord le tableau, deux pointeurs partant des deux extrémités permettent de résoudre le problème en un seul parcours. Le tri coûte O(n log n), puis le parcours coûte O(n).
a.sort()
left, right = 0, len(a) - 1Comparer à la cible
À chaque étape, lisez a[left] + a[right]. Ce nombre unique détermine votre prochain déplacement, sans aucune approximation.
total = a[left] + a[right]Correspondance exacte : terminé
Si la somme est égale à la cible, vous avez trouvé la paire. Retournez-la immédiatement, car une seule réponse valide vous suffit.
if total == target:
return (left, right)Sinon, ajuster
Si la somme est trop petite, déplacez left vers la droite ; si elle est trop grande, déplacez right vers la gauche. L’ordre trié garantit que chaque déplacement vous rapproche du but.
elif total < target:
left += 1
else:
right -= 1Aucune paire n’existe
Si les pointeurs se croisent sans correspondance, aucune paire valide n’existe. La fin de la boucle constitue en elle-même une réponse complète.
L’alternative avec un ensemble de hachage
Si vous devez conserver les indices d’origine, un ensemble de hachage est plus simple : pour chaque valeur, vérifiez si la cible moins cette valeur a déjà été rencontrée.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Choisir votre méthode
Utilisez les deux pointeurs lorsque le tableau est déjà trié ou peut l’être ; utilisez l’ensemble de hachage lorsque vous avez besoin d’une complexité réellement en O(n) sans tri ou que vous devez conserver les indices.
Surveiller les doublons
Si une valeur peut être associée à elle-même, assurez-vous que vos deux indices sont différents. Une vérification rapide avec left != right ou i != j évite ce piège.
Vérification rapide
Vous voulez faire mieux que la force brute en O(n^2) pour trouver une paire dont la somme atteint une cible.
Récapitulatif
Triez puis parcourez le tableau avec deux pointeurs pour trouver une paire cible en O(n log n), ou utilisez un ensemble de hachage en O(n) lorsque les indices sont importants. Choisissez selon les contraintes. ✅
Questions Fréquemment Posées
La leçon « Trouver une paire d’une somme donnée » est-elle gratuite ?
Oui — le texte complet de « Trouver une paire d’une somme donnée » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Trouver une paire d’une somme donnée » ?
Faire mieux que la force brute en O(n^2) Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 2 sur 4.
Combien de temps prend la leçon « Trouver une paire d’une somme donnée » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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
- Deux pointeurs sur un tableau trié
- Trouver une paire d’une somme donnée
- Supprimer les doublons sur place
- Fusionner deux séquences triées