Two Sum II: Sorted Input
Vous recevez un tableau d’entiers numbers trié par ordre non décroissant, ainsi qu’un entier target. Une seule paire de positions distinctes contient deux valeurs dont la somme est égale à target. Renvoyez ces deux positions sous forme d’indices commençant à 0, en plaçant le plus petit indice en premier.
Fonction
- numbersinteger-array
- le tableau trié d’entiers
- targetinteger
- la somme des deux valeurs doit atteindre
- Renvoieinteger-array
- les deux indices à base zéro [i, j] tels que i < j et numbers[i] + numbers[j] == target
Contraintes
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersest trié par ordre non décroissant.- Il existe exactement une paire d’indices
i < jtelle quenumbers[i] + numbers[j] == target.
Exemples
- Entrée
- numbers = [-4, 1, 3, 8, 12]target = 9
- Sortie
- [1, 3]
- Explication
- 1 se trouve à l’indice 1 et 8 à l’indice 3, et 1 + 8 = 9. Aucune autre paire n’atteint 9 : par exemple, -4 + 12 = 8.
- Entrée
- numbers = [2, 2, 5, 7]target = 4
- Sortie
- [0, 1]
- Explication
- Les deux 2 aux indices 0 et 1 correspondent à deux positions différentes, ils peuvent donc former la paire : 2 + 2 = 4.
- Entrée
- numbers = [-10, -3, 0, 6]target = -4
- Sortie
- [0, 3]
- Explication
- -10 à l’index 0 et 6 à l’index 3 donnent -10 + 6 = -4. La réponse peut couvrir tout le tableau.
+13 tests cachés à la soumission
Pour aller plus loin
Peux-tu résoudre ce problème en O(n) avec O(1) mémoire supplémentaire ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Le tableau est trié. Regardez ensemble la plus petite et la plus grande valeur. Que vous indique leur somme lorsqu’elle est inférieure à
target?Si la première valeur additionnée à la dernière est trop petite, la première valeur est trop petite pour tous ses partenaires, car la dernière valeur est déjà la plus grande. Tu peux l’éliminer.
Gardez un pointeur à chaque extrémité. Lorsque la somme est trop petite, déplacez le pointeur de gauche vers la droite ; lorsqu’elle est trop grande, déplacez le pointeur de droite vers la gauche. Arrêtez-vous lorsque la somme est égale à
target.
Solution
Une table de hachage résout la version non triée en un seul parcours, mais elle nécessite O(n) de mémoire. Ici, le tableau est trié, et cet ordre vous indique dans quelle direction avancer. Placez un pointeur à chaque extrémité. Si la somme est trop petite, seule une valeur plus grande à gauche peut aider ; si elle est trop grande, seule une valeur plus petite à droite peut aider. À chaque étape, vous éliminez définitivement une valeur, donc un seul parcours suffit à trouver la paire sans mémoire supplémentaire.
Vérifiez chaque paire
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Essaie chaque paire de positions i < j et vérifie si numbers[i] + numbers[j] est égal à target. Comme i avance depuis la gauche et que j commence juste après, la première paire trouvée a déjà le plus petit indice en premier.
C’est correct, mais cela ne tient pas compte de l’ordre trié. Avec n = 10^4, il y a environ 5 × 10^7 paires et, lorsque la réponse se trouve près de la fin du tableau, tu en testes presque toutes. C’est trop lent pour les grands tests.
Algorithme
- Parcourez chaque indice avec la boucle
i. - Parcourez avec
jles indices dei+1jusqu’au dernier indice. - Si
numbers[i] + numbers[j]est égal àtarget, renvoyez[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Recherche binaire pour chaque partenaire
Intuition
Une fois que tu as fixé la première valeur numbers[i], tu connais exactement sa partenaire : target - numbers[i]. La partie du tableau située à droite de i est triée, donc la recherche binaire peut déterminer en O(log n) étapes si cette partenaire s’y trouve.
Pour [-4, 1, 3, 8, 12] et target = 9 : à i = 0, la partenaire serait 13, qui est absente. À i = 1, la partenaire est 8, et la recherche la trouve à l’index 3. La réponse est [1, 3].
Ne chercher qu’à droite de i place le plus petit index en premier et empêche une valeur de s’associer à elle-même. La paire est unique, donc la valeur partenaire apparaît au plus une fois dans cette plage et toute correspondance est la réponse. Au total : n recherches de O(log n) chacune.
Algorithme
- Parcourez
ide 0 àn-2. - Calculez
need = target - numbers[i]. - Recherchez
needpar recherche binaire dans les indices dei+1àn-1. - Si vous le trouvez à
mid, renvoyez[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Deux pointeurs depuis les deux extrémités
Intuition
Commence avec left = 0 et right = n-1, puis examine numbers[left] + numbers[right]. Si la somme est égale à target, tu as terminé. Si elle est trop petite, numbers[left] ne peut pas faire partie de la réponse : même associé à la plus grande valeur encore en jeu, il ne suffit pas. Déplace donc left vers la droite. Si la somme est trop grande, numbers[right] ne peut pas non plus en faire partie, car même associé au plus petit partenaire restant, le résultat est trop élevé. Déplace donc right vers la gauche.
Chaque déplacement élimine une valeur qui ne peut jamais faire partie de la paire, et la paire elle-même n'est jamais éliminée. Les pointeurs se rejoignent après au plus n-1 déplacements : le parcours est donc en O(n) et utilise deux variables.
Avec [-4, 1, 3, 8, 12] et target = 9 : -4 + 12 = 8 est trop petit, donc left passe à l'indice 1. Ensuite, 1 + 12 = 13 est trop grand, donc right passe à l'indice 3. Maintenant, 1 + 8 = 9, et la réponse est [1, 3].
Algorithme
- Définissez
leftà 0 etrightàn-1. - Tant que
left < right, calculeztotal = numbers[left] + numbers[right]. - Si
totalest égal àtarget, renvoyez[left, right]. - Si
totalest plus petit, ajoutez 1 àleft; s’il est plus grand, soustrayez 1 àright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Pièges et cas limites
La boucle à deux pointeurs est courte, donc les bugs se cachent dans les détails qui l’entourent.
- Renvoyer des positions indexées à partir de 1. Cette version veut des indices indexés à partir de 0 : pour
[-4, 1, 3, 8, 12]ettarget = 9, la réponse est[1, 3], et non[2, 4]. En Lua et en R, soustrayez 1 avant de renvoyer le résultat. - Répéter la boucle avec
left <= right. Lorsque les pointeurs se rejoignent, la somme utiliserait deux fois la même valeur. - Déplacer le mauvais pointeur. Une somme trop petite nécessite une valeur plus grande, et seul
leftpeut en fournir une. - Rejeter les valeurs en double. Avec
[2, 2, 5, 7]ettarget = 4, on utilise les deux 2, qui se trouvent à des positions différentes. - Débordement. Les limites ici garantissent que chaque somme tient dans un entier de 32 bits. Si les valeurs pouvaient atteindre
10^9, additionnez-les dans un type 64 bits.
Questions fréquentes4
Pourquoi deux pointeurs fonctionnent-ils pour résoudre Two Sum dans un tableau trié ?
Lorsque la somme des deux extrémités est trop petite, la valeur de gauche est trop petite pour tous les partenaires encore en jeu, car l’extrémité droite est la plus grande d’entre eux. Tu peux l’éliminer définitivement. Le même raisonnement permet d’éliminer la valeur de droite lorsque la somme est trop grande. La paire correspondant à la réponse n’est jamais éliminée, donc les pointeurs finissent par se rejoindre dessus.
Quelle est la complexité temporelle de Two Sum II ?
La solution à deux pointeurs s’exécute en temps O(n) et utilise un espace supplémentaire O(1) : à chaque étape, un pointeur se déplace vers l’intérieur, et les deux se rejoignent après au plus n-1 étapes. Effectuer une recherche binaire pour chaque partenaire prend O(n log n), et vérifier chaque paire prend O(n²).
Pourquoi ne pas utiliser une table de hachage comme dans le premier problème Two Sum ?
Une table de hachage fonctionne également et s’exécute en temps O(n), mais elle stocke jusqu’à n valeurs. L’ordre trié rend cette mémoire inutile : les deux pointeurs savent dans quelle direction avancer en se basant uniquement sur la somme. Les recruteurs posent cette question pour voir si tu utilises l’ordre qui t’a été donné.
Quand la recherche binaire est-elle le meilleur choix ici ?
Lorsqu’une valeur est fixe et que tu as seulement besoin de sa partenaire. Si numbers[0] doit faire partie de la paire, une recherche binaire permet de trouver l’autre indice en O(log n). Pour trouver une paire inconnue, le parcours avec deux pointeurs est plus rapide que n recherches distinctes.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def twoSumSorted(numbers, target):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
numbers = [-4, 1, 3, 8, 12] target = 9
Attendu
[1, 3]