Two Sum
Otrzymujesz listę liczb całkowitych i wartość docelową. Dokładnie dwie liczby z listy sumują się do wartości docelowej, a Twoim zadaniem jest podać ich pozycje.
Weź nums = [3, 8, 12, 5] i target = 17. Wartość 12 znajduje się pod indeksem 2, a 5 pod indeksem 3, a 12 + 5 = 17, więc odpowiedzią jest [2, 3].
Te dwie liczby muszą pochodzić z dwóch różnych pozycji. W [4, 2, 6] przy target = 8 nie wolno użyć liczby 4 dwa razy; odpowiedzią jest [1, 2], ponieważ 2 + 6 = 8. Ta sama wartość może jednak wystąpić dwa razy: w [7, 3, 7] przy target = 14 odpowiedzią jest [0, 2].
Napisz funkcję o nazwie twoSum, która otrzymuje tablicę liczb całkowitych nums oraz liczbę całkowitą target i zwraca tablicę z dwoma indeksami [i, j], takimi że nums[i] + nums[j] jest równe target.
Indeksy muszą wskazywać dwie różne pozycje i być zwrócone w kolejności rosnącej (i jest mniejsze od j). Każde dane wejściowe zawierają dokładnie jedną taką parę.
Ograniczenia: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Funkcja
- arg1integer-array
- arg2integer
- Zwracainteger-array
Przykłady
- Wejście
- arg1 = [3, 8, 12, 5]arg2 = 17
- Wyjście
- [2, 3]
- Wejście
- arg1 = [6, 1, 4, 10]arg2 = 7
- Wyjście
- [0, 1]
- Wejście
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Wyjście
- [1, 2]
+13 ukrytych testów przy wysłaniu
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Sprawdzanie każdej pary za pomocą dwóch zagnieżdżonych pętli jest poprawne, ale dla 10 000 liczb oznacza około 50 milionów sprawdzeń. Czy potrafisz znaleźć liczbę, która dopełnia każdą liczbę do wymaganej sumy, bez ponownego przeszukiwania listy?
Gdy stoisz na wartości
x, wiesz już, jaka wartość uzupełni parę: cel minusx. Jedyne pytanie brzmi, czy wcześniej napotkałeś tę wartość i pod jakim indeksem.Przejdź przez listę raz i przechowuj w mapie haszującej każdą napotkaną wartość wraz z jej indeksem. Na każdej pozycji najpierw wyszukaj brakującą wartość do pary; jeśli znajduje się w mapie, masz oba indeksy. W przeciwnym razie zapisz bieżącą wartość i przejdź dalej. Wyszukiwanie przed zapisaniem zapobiega parowaniu liczby z samą sobą.
Pełne omówienie tego zadania pojawi się wkrótce.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def twoSum(nums, target):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
arg1 = [3, 8, 12, 5] arg2 = 17
Oczekiwane
[2, 3]