Two-Sum et ses nombreuses variantes

Le problème 1 de LeetCode, « Somme de deux nombres » : étant donné un tableau non trié et une cible, renvoyez les indices de deux éléments dont la somme est égale à la cible. L’approche par force brute en O(n²) examine toutes les paires. L’approche optimale en O(n) utilise une table de hachage : pour chaque élément x, vérifiez si target - x existe déjà dans la table. Si oui, renvoyez la paire d’indices. Sinon, stockez x et son indice dans la table.

La somme de deux nombres est souvent le tout premier problème posé lors d’un entretien — le maîtriser parfaitement montre que vous êtes prêt à passer à des problèmes plus difficiles.

La table de hachage stocke chaque élément rencontré jusqu’à présent. Lors du traitement de l’élément x, si target - x se trouve dans la table, ces deux éléments forment une paire valide. Point essentiel, le complément est toujours vérifié avant que x soit stocké, ce qui évite qu’un élément soit associé à lui-même (par exemple, si x == target/2, la vérification de la table a lieu avant le stockage de x ; il ne correspondra donc pas, sauf s’il existe deux copies).

Si le tableau est déjà trié et que vous avez besoin des indices des valeurs (et non des indices d’origine), utilisez la technique des deux pointeurs : des pointeurs gauche et droit partant des extrémités opposées. Si la somme est égale à la cible, renvoyez le résultat. Si la somme est trop petite, déplacez le pointeur gauche vers la droite. Si elle est trop grande, déplacez le pointeur droit vers la gauche. Cette méthode s’exécute en O(n) et utilise un espace O(1) — elle est préférable à l’approche par table de hachage lorsque le tableau est trié et que la mémoire est limitée.

Le problème 15 de LeetCode, « Somme de trois nombres » : trouvez tous les triplets distincts dont la somme est nulle. Triez le tableau, fixez un élément à la fois, puis appliquez la technique des deux pointeurs au sous-tableau trié restant. Ignorez les valeurs en double pour éviter les triplets dupliqués. Complexité temporelle : O(n²) — optimale pour ce problème, puisque la sortie elle-même peut contenir O(n²) triplets.

Le problème 18 de LeetCode, « Somme de quatre nombres » : trouvez tous les quadruplets distincts dont la somme est égale à la cible. Étendez la somme de trois nombres : fixez deux éléments à l’aide de deux boucles imbriquées (en ignorant les doublons), puis appliquez la technique des deux pointeurs au sous-tableau intérieur. Complexité temporelle : O(n³). Pour une somme de k nombres en général, répétez la récursion k-2 fois, puis appliquez la technique des deux pointeurs, ce qui donne une complexité temporelle en O(n^(k-1)).

Une variante courante consiste à trouver la paire dont la somme est la plus proche de la cible (sans nécessairement lui être exactement égale). Triez le tableau et utilisez deux pointeurs. Suivez la somme la plus proche rencontrée jusqu’à présent et mettez-la à jour chaque fois que vous trouvez une paire dont l’écart absolu avec la cible est plus petit. Cette approche en O(n log n) est simple à appliquer après le tri.

Pour trouver toutes les paires dont la somme est égale à une cible, triez le tableau et utilisez deux pointeurs en recueillant toutes les paires. Après avoir trouvé une paire valide, ignorez les doublons des deux côtés avant de continuer. Cela donne O(n log n) pour le tri, plus O(n) pour le parcours — soit O(n log n) au total. Utiliser une table de hachage pour recueillir les paires est également valable, mais nécessite de gérer soigneusement les doublons.

Une autre variante consiste à compter le nombre de paires dont la somme est inférieure à k. Triez le tableau et utilisez deux pointeurs. Lorsque nums[lo] + nums[hi] < k, toutes les paires (lo, lo+1), (lo, lo+2), ..., (lo, hi) sont valides — il s’agit de hi - lo paires. Avancez lo. Sinon, réduisez hi. Temps total : O(n log n) pour le tri, plus O(n) pour le comptage.

Lorsque la même valeur peut apparaître plusieurs fois et que vous devez compter les paires valides (et pas seulement vérifier leur existence), stockez les fréquences dans la table. Pour les paires dont les deux éléments sont égaux, le nombre de paires correspondant à une fréquence f est f*(f-1)//2. Pour les paires dont les deux éléments sont différents, multipliez leurs fréquences. Cela permet de compter toutes les paires valides en O(n).

Le schéma de la somme de deux nombres apparaît sous de nombreuses formes. Reconnaissez-le lorsqu’un problème demande de trouver au moins deux éléments satisfaisant une relation numérique (somme, produit, différence). La stratégie fondamentale est toujours la même : fixer un élément, puis trouver son complément dans une structure précalculée (table de hachage ou tableau trié accompagné d’un pointeur). Étendez-la à la somme de k nombres en fixant k-2 éléments avec des boucles imbriquées, puis en appliquant le cas de base.

Lorsque le problème de la somme de deux nombres se présente en entretien, expliquez votre raisonnement à voix haute : « Je dois trouver deux nombres dont la somme est égale à la cible. Pour chaque nombre x, je dois vérifier si cible-x existe. Je peux répondre à cette question en O(1) avec une table de hachage, pour un temps total de O(n) et un espace de O(n). Autrement, si le tableau était trié, je pourrais utiliser deux pointeurs avec un espace O(1). » Présentez les deux approches et demandez s’il existe des contraintes d’espace avant de faire votre choix.

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

Dans cette leçon, vous avez appris : le problème des deux sommes utilise une table de hachage pour vérifier l’existence du complément en O(1), ce qui donne une complexité globale de O(n), pour les tableaux triés, la méthode des deux pointeurs atteint une complexité spatiale de O(1), et les problèmes des trois sommes et des quatre sommes se ramènent au problème des deux sommes grâce au tri et à des boucles imbriquées, avec des complexités respectives de O(n²) et O(n³). Ensuite, nous étudierons les schémas de comptage des fréquences et le regroupement avec defaultdict et Counter.