Two Sum
Du erhältst eine Liste ganzer Zahlen und einen Zielwert. Genau zwei Zahlen in der Liste ergeben zusammen den Zielwert, und deine Aufgabe ist es, ihre Positionen anzugeben.
Nimm nums = [3, 8, 12, 5] und target = 17. Der Wert 12 steht am Index 2 und 5 am Index 3, und 12 + 5 = 17, also lautet die Antwort [2, 3].
Die beiden Zahlen müssen von zwei verschiedenen Positionen stammen. In [4, 2, 6] mit target = 8 ist es nicht erlaubt, die 4 zweimal zu verwenden; die Antwort lautet [1, 2], weil 2 + 6 = 8. Derselbe Wert kann jedoch zweimal vorkommen: In [7, 3, 7] mit target = 14 lautet die Antwort [0, 2].
Schreibe eine Funktion namens twoSum, die ein Array mit ganzen Zahlen nums und eine ganze Zahl target erhält und ein Array mit zwei Indizes [i, j] zurückgibt, sodass nums[i] + nums[j] gleich target ist.
Die Indizes müssen zwei verschiedene Positionen bezeichnen und in aufsteigender Reihenfolge zurückgegeben werden (i ist kleiner als j). Für jede Eingabe gibt es genau ein solches Paar.
Einschränkungen: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Funktion
- arg1integer-array
- arg2integer
- Gibt zurückinteger-array
Beispiele
- Eingabe
- arg1 = [3, 8, 12, 5]arg2 = 17
- Ausgabe
- [2, 3]
- Eingabe
- arg1 = [6, 1, 4, 10]arg2 = 7
- Ausgabe
- [0, 1]
- Eingabe
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Ausgabe
- [1, 2]
+13 versteckte Tests beim Einreichen
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 bei einem Wert
xstehst, weißt du bereits, welcher Wert das Paar vervollständigen würde: das Ziel minusx. Die einzige Frage ist, ob du diesem Wert bereits zuvor begegnet bist und an welchem Index.Durchlaufe die Liste einmal und behalte eine Hash-Map mit jedem Wert, den du bereits passiert hast, und seinem Index. Suche an jeder Position zuerst nach dem fehlenden Partner; ist er in der Map, hast du beide Indizes. Andernfalls speichere den aktuellen Wert und fahre fort. Die Suche vor dem Speichern verhindert, dass sich eine Zahl mit sich selbst paart.
Eine vollständige Lösungserklärung zu dieser Aufgabe folgt bald.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def twoSum(nums, target):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
arg1 = [3, 8, 12, 5] arg2 = 17
Erwartet
[2, 3]