Two Sum
Du erhältst ein Array aus ganzen Zahlen nums und eine ganze Zahl target. Genau zwei Einträge von nums an zwei verschiedenen Positionen ergeben zusammen target. Gib die Indizes dieser beiden Einträge zurück, zuerst den kleineren Index.
Funktion
- numsinteger-array
- das Array von Ganzzahlen, das durchsucht werden soll
- targetinteger
- die Summe, die die beiden Einträge erreichen müssen
- Gibt zurückinteger-array
- die beiden Indizes, der kleinere zuerst
Einschränkungen
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- Genau ein Paar verschiedener Positionen ergibt zusammen
target.
Beispiele
- Eingabe
- nums = [3, 8, 12, 5]target = 17
- Ausgabe
- [2, 3]
- Erklärung
- 12 steht am Index 2 und 5 am Index 3, und 12 + 5 = 17. Kein anderes Paar ergibt 17.
- Eingabe
- nums = [6, 1, 4, 10]target = 7
- Ausgabe
- [0, 1]
- Erklärung
- 6 am Index 0 und 1 am Index 1 ergeben zusammen 7: Das Paar kann die ersten beiden Einträge bilden.
- Eingabe
- nums = [2, -6, 9, 4, 13]target = 3
- Ausgabe
- [1, 2]
- Erklärung
- -6 an Index 1 und 9 an Index 2 ergeben zusammen 3. Negative Zahlen bilden genauso Paare wie positive Zahlen.
Weiterführende Frage
Wenn nums bereits sortiert wäre, könntest du das Paar in O(n)-Zeit und mit nur O(1) zusätzlichem Speicher finden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Jedes Paar mit zwei verschachtelten Schleifen auszuprobieren ist korrekt, aber bei 10.000 Zahlen sind das etwa 50 Millionen Prüfungen. Kannst du zu jeder Zahl den passenden Partner finden, ohne die Liste erneut zu durchsuchen?
Wenn du auf einem Wert
xstehst, weißt du bereits, welcher Wert das Paar vervollständigen würde: das Ziel minusx. Die einzige Frage ist, ob du diesen Wert bereits zuvor passiert hast und an welchem Index.Durchlaufe die Liste einmal und speichere in einer Hash-Map jeden Wert, den du bereits durchlaufen hast, zusammen mit seinem Index. Suche an jeder Position zuerst nach dem fehlenden Gegenwert; befindet er sich in der Map, hast du beide Indizes. Andernfalls speichere den aktuellen Wert und fahre fort. Die Suche vor dem Speichern verhindert, dass eine Zahl mit sich selbst gepaart wird.
Lösung
Jedes Zahlenpaar zu überprüfen funktioniert, aber der Aufwand wächst mit dem Quadrat der Länge. Dreh die Frage um: Wenn du bei einer Zahl x bist, weißt du bereits, dass ihr Gegenstück target - x sein muss. Eine Hash-Map zeigt dir in konstanter Zeit, ob du diesen Wert bereits passiert hast, sodass ein Durchlauf genügt.
Überprüfe jedes Paar
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Lege einen ersten Index i fest und probiere jeden Index j rechts davon aus, bis nums[i] + nums[j] gleich target ist. Wenn du j bei i + 1 beginnen lässt, kann eine Position nicht mit sich selbst gepaart werden, jedes Paar wird genau einmal ausprobiert und der kleinere Index steht zuerst. Das gesuchte Paar ist eines der Paare, die du ausprobierst, also findest du es.
n Zahlen ergeben etwa n²/2 Paare: Bei n = 10^4 sind das fast 5 × 10^7 Additionen.
Algorithmus
- Durchlaufe
ifür jeden Index vonnums. - Durchlaufe für jedes
ijvoni + 1bis zum letzten Index. - Wenn
nums[i] + nums[j]gleichtargetist, gib[i, j]zurück. - Wenn beide Schleifen beendet sind, gib ein leeres Array zurück. Das Problem garantiert, dass dies niemals passiert.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []Ein Durchlauf mit einer Hash-Map
Idee
Für ein festes nums[i] sucht die innere Schleife der Brute-Force-Lösung nach einem Wert, den du bereits kennst: target - nums[i]. Diese Suche ist im Grunde eine Lookup-Operation, und eine Hash-Map von Werten zu Indizes ermöglicht Lookups, die durchschnittlich konstante Zeit benötigen.
Zuerst nachschlagen, dann speichern. So kann eine Zahl nur mit einer Zahl davor ein Paar bilden, niemals mit sich selbst, und da der Partner immer früher kommt, steht sein Index zuerst. Jede Zahl wird einmal mit Map-Operationen in konstanter Zeit verarbeitet, daher ist die Suche O(n); der Preis dafür ist eine Map mit bis zu n Einträgen.
Algorithmus
- Erstelle eine leere Zuordnung von Werten zu Indizes.
- Berechne für jeden Index
ineed, den Wert, der das Paar vervollständigt:targetminusnums[i]. - Wenn
needin der Zuordnung enthalten ist, gib den gespeicherten Index gefolgt vonizurück. - Andernfalls speichere
nums[i]mit dem Indexiund fahre fort.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
Stolperfallen und Grenzfälle
- Eine Zahl speichern, bevor nach ihrem Gegenstück gesucht wird. Bei
[4, 2, 6]undtarget = 8findet die 4 sich selbst, und du gibst[0, 0]zurück. - Die Indizes in der falschen Reihenfolge zurückgeben. Bei der Suche vor dem Speichern ist der Index aus der Map der kleinere und kommt zuerst.
- Das Array sortieren, um zwei Zeiger zu verwenden, und dann Positionen in der sortierten Kopie zurückgeben. Behalte den ursprünglichen Index neben jedem Wert bei.
- Annehmen, dass die Werte positiv oder verschieden sind. Bei
[0, 7, -3, 0]undtarget = 0bilden die beiden Nullen ein Paar:[0, 3]. - In Lua und R die 1-basierten Indizes zurückgeben. Ziehe von jedem 1 ab.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität von Two Sum?
Die Hash-Map-Lösung benötigt O(n) Zeit, da sie jede Zahl einmal durchläuft und jede Suche oder Einfügung im Durchschnitt konstante Zeit benötigt. Für die Map verwendet sie zusätzlich O(n) Speicherplatz. Jedes Zahlenpaar zu überprüfen, benötigt O(n²) Zeit und O(1) Speicherplatz.
Kann Two Sum ohne zusätzlichen Speicherplatz gelöst werden?
Nicht in linearer Zeit bei einem unsortierten Array. Mit O(1) zusätzlichem Speicherplatz musst du wieder jedes Paar überprüfen, was O(n²) entspricht. Die Hash-Map tauscht O(n) Speicher gegen lineare Laufzeit.
Wie geht Two Sum mit doppelten Zahlen um?
Duplikate funktionieren, wenn du den passenden Wert nachschlägst, bevor du die aktuelle Zahl speicherst. Bei [7, 3, 7] mit target = 14 wird die erste 7 an Index 0 gespeichert, und die zweite 7 findet sie, sodass [0, 2] zurückgegeben wird. Eine einzelne 7 bildet nie ein Paar mit sich selbst: Beim Nachschlagen ist sie noch nicht in der Map.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def twoSum(nums, target):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums = [3, 8, 12, 5] target = 17
Erwartete Ausgabe
[2, 3]