Two Sum

Q: Jaka jest złożoność czasowa problemu Two Sum?

Rozwiązanie z użyciem mapy haszującej działa w czasie O(n) , ponieważ odwiedza każdą liczbę raz, a każde wyszukiwanie lub wstawienie zajmuje średnio stały czas. Mapa zajmuje dodatkowe miejsce O(n) . Sprawdzenie każdej pary zajmuje czas O(n²) i miejsce O(1) .

ŁatweHaszowanie

+10

Otrzymujesz tablicę liczb całkowitych nums oraz liczbę całkowitą target. Dokładnie dwa elementy tablicy nums na dwóch różnych pozycjach sumują się do target. Zwróć indeksy tych dwóch elementów, zaczynając od mniejszego indeksu.

Funkcja

twoSum(nums: integer-array, target: integer) → integer-array

numsinteger-array: tablica liczb całkowitych do przeszukania
targetinteger: suma, do której muszą dojść te dwa wpisy
Zwracainteger-array: dwa indeksy, najpierw mniejszy

Ograniczenia

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
Dokładnie jedna para różnych pozycji sumuje się do target.

Przykłady

Wejście: nums = [3, 8, 12, 5]target = 17
Wyjście: [2, 3]
Wyjaśnienie: 12 znajduje się pod indeksem 2, a 5 pod indeksem 3, i 12 + 5 = 17. Żadna inna para nie daje w sumie 17.

Pytanie dodatkowe

Gdyby nums były już posortowane, czy udałoby Ci się znaleźć parę w czasie O(n), używając tylko O(1) dodatkowej pamięci?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Sprawdzanie każdej pary działa, ale nakład pracy rośnie proporcjonalnie do kwadratu długości. Odwróć pytanie: mając liczbę x, wiesz już, że jej partnerem musi być target - x. Tablica mieszająca pozwala w stałym czasie sprawdzić, czy już minąłeś tę wartość, więc wystarczy jedno przejście.

Sprawdź każdą parę

Poprawne, ale nie kończy się na największych testach

Intuicja

Ustal pierwszy indeks i i wypróbuj każdy indeks j na prawo od niego, aż nums[i] + nums[j] będzie równe target. Rozpoczęcie od j równego i + 1 zapobiega łączeniu pozycji z samą sobą, pozwala wypróbować każdą parę tylko raz i umieszcza mniejszy indeks jako pierwszy. Szukana para jest jedną z wypróbowywanych par, więc ją znajdziesz.

n liczb tworzy około n²/2 par: dla n = 10^4 oznacza to blisko 5 × 10^7 dodawań.

Algorytm

Iteruj po każdym indeksie tablicy nums za pomocą i.
Dla każdego i iteruj za pomocą j od i + 1 do ostatniego indeksu.
Jeśli nums[i] + nums[j] jest równe target, zwróć [i, j].
Jeśli obie pętle się zakończą, zwróć pustą tablicę. Treść zadania gwarantuje, że to się nigdy nie zdarzy.

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 []

Jedno przejście z użyciem mapy haszującej

Intuicja

Dla ustalonego nums[i] wewnętrzna pętla metody brute force szuka jednej wartości, którą znasz z góry: target - nums[i]. To skanowanie jest w rzeczywistości wyszukiwaniem, a mapa haszująca odwzorowująca wartości na indeksy pozwala średnio wyszukiwać w stałym czasie.

Najpierw wyszukaj, potem zapisz. Wtedy liczba może utworzyć parę tylko z czymś, co wystąpiło wcześniej, nigdy z samą sobą, a ponieważ partner zawsze znajduje się wcześniej, jego indeks jest pierwszy. Każda liczba jest odwiedzana raz, a operacje na mapie zajmują stały czas, więc wyszukiwanie ma złożoność O(n); kosztem jest mapa zawierająca do n wpisów.

Algorytm

Utwórz pustą mapę przypisującą wartości do indeksów.
Dla każdego indeksu i oblicz need, czyli wartość, która uzupełnia parę: target minus nums[i].
Jeśli need znajduje się w mapie, zwróć zapisany indeks, a następnie i.
W przeciwnym razie zapisz nums[i] wraz z indeksem i i kontynuuj.

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 []

Pułapki i przypadki brzegowe

Zapisywanie liczby przed sprawdzeniem, jaka liczba do niej pasuje. Dla [4, 2, 6] i target = 8 liczba 4 pasuje do samej siebie, więc zwracasz [0, 0].
Zwracanie indeksów w niewłaściwej kolejności. Gdy najpierw sprawdzasz, a potem zapisujesz, indeks z mapy jest mniejszy i powinien być pierwszy.
Sortowanie tablicy, aby użyć dwóch wskaźników, a następnie zwracanie pozycji z posortowanej kopii. Zachowaj oryginalny indeks obok każdej wartości.
Zakładanie, że wartości są dodatnie lub różne. Dla [0, 7, -3, 0] i target = 0 parę tworzą dwie zera: [0, 3].
W Lua i R zwracanie indeksów numerowanych od 1. Odejmij 1 od każdego z nich.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Two Sum?

Rozwiązanie z użyciem mapy haszującej działa w czasie O(n), ponieważ odwiedza każdą liczbę raz, a każde wyszukiwanie lub wstawienie zajmuje średnio stały czas. Mapa zajmuje dodatkowe miejsce O(n). Sprawdzenie każdej pary zajmuje czas O(n²) i miejsce O(1).

Czy problem Two Sum można rozwiązać bez dodatkowej pamięci?

Nie w czasie liniowym w nieposortowanej tablicy. Przy dodatkowej przestrzeni O(1) znów musisz sprawdzać każdą parę, co zajmuje O(n²). Mapa haszująca wymienia pamięć O(n) na czas liniowy.

Jak Two Sum obsługuje zduplikowane liczby?

Duplikaty działają, gdy wyszukujesz pasującą liczbę przed zapisaniem bieżącej. W [7, 3, 7] przy target = 14 pierwsza 7 zostaje zapisana pod indeksem 0, a druga 7 ją znajduje, dając [0, 2]. Pojedyncza 7 nigdy nie tworzy pary sama ze sobą: nie ma jej jeszcze w mapie, gdy jej szukasz.

def twoSum(nums, target):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

nums = [3, 8, 12, 5]
target = 17

Oczekiwany wynik

[2, 3]