Two Sum II: Sorted Input

Q: Dlaczego dwa wskaźniki działają w przypadku problemu Two Sum na posortowanej tablicy?

Gdy suma dwóch końców jest zbyt mała, lewa wartość jest zbyt mała dla każdego partnera, który nadal pozostaje w grze, ponieważ prawy koniec jest największy z nich. Możesz ją na stałe odrzucić. Ten sam argument pozwala odrzucić prawą wartość, gdy suma jest zbyt duża. Para będąca odpowiedzią nigdy nie zostaje odrzucona, więc wskaźniki kończą na niej.

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

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) i wymaga O(1) dodatkowej pamięci: w każdym kroku jeden wskaźnik przesuwa się do środka, a wskaźniki spotykają się po co najwyżej n-1 krokach. Wyszukiwanie binarne każdego pasującego elementu zajmuje O(n log n) , a sprawdzenie każdej pary zajmuje O(n²) .

Q: Dlaczego nie użyć mapy haszującej, tak jak w pierwszym zadaniu Two Sum?

Mapa mieszająca działa i również działa w czasie O(n) , ale przechowuje do n wartości. Posortowana kolejność sprawia, że ta pamięć jest zbędna: same wskaźniki wiedzą, w którą stronę się przesunąć, na podstawie samej sumy. Rekruterzy zadają to pytanie, aby sprawdzić, czy korzystasz z podanej kolejności.

Q: Kiedy wyszukiwanie binarne jest tu lepszym wyborem?

Gdy jedna wartość jest ustalona i potrzebujesz tylko jej pary. Jeśli numbers[0] musi znaleźć się w parze, jedno wyszukiwanie binarne znajduje drugi indeks w czasie O(log n) . Aby znaleźć nieznaną parę, skanowanie dwoma wskaźnikami jest szybsze niż n oddzielnych wyszukiwań.

ŁatweDwa wskaźniki Wyszukiwanie binarne

+10

Otrzymujesz tablicę liczb całkowitych numbers posortowaną w kolejności niemalejącej oraz liczbę całkowitą target. Dokładnie jedna para różnych pozycji zawiera dwie wartości, które sumują się do target. Zwróć te dwie pozycje jako indeksy liczone od 0, najpierw mniejszy indeks.

Funkcja

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: posortowana tablica liczb całkowitych
targetinteger: suma, jaką muszą osiągnąć te dwie wartości
Zwracainteger-array: dwa indeksy liczone od 0 [i, j], gdzie i < j i numbers[i] + numbers[j] == target

Ograniczenia

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers jest posortowana w kolejności nierosnącej.
Dokładnie jedna para indeksów i < j spełnia warunek numbers[i] + numbers[j] == target.

Przykłady

Wejście: numbers = [-4, 1, 3, 8, 12]target = 9
Wyjście: [1, 3]
Wyjaśnienie: 1 znajduje się pod indeksem 1, a 8 pod indeksem 3, i 1 + 8 = 9. Żadna inna para nie daje 9: na przykład -4 + 12 = 8.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz rozwiązać to w czasie O(n) i przy użyciu O(1) dodatkowej pamięci?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Mapa haszująca rozwiązuje problem w wersji nieposortowanej w jednym przebiegu, ale wymaga O(n) pamięci. Tutaj tablica jest posortowana, a jej kolejność podpowiada, w którą stronę się przesuwać. Umieść jeden wskaźnik na każdym końcu. Jeśli suma jest za mała, pomóc może tylko większa wartość po lewej stronie; jeśli jest za duża — tylko mniejsza wartość po prawej. Każdy krok definitywnie wyklucza jedną wartość, więc jeden przebieg pozwala znaleźć parę bez dodatkowej pamięci.

Sprawdź każdą parę

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

Intuicja

Sprawdź każdą parę pozycji i < j i przetestuj, czy numbers[i] + numbers[j] jest równe target. Ponieważ i przesuwa się od lewej, a j zaczyna tuż za nim, pierwsza znaleziona para ma już mniejszy indeks jako pierwszy.

To poprawne rozwiązanie, ale nie wykorzystuje posortowanej kolejności. Dla n = 10^4 istnieje około 5 × 10^7 par, a gdy odpowiedź znajduje się blisko końca tablicy, sprawdzasz niemal wszystkie z nich. To zbyt wolne dla dużych testów.

Algorytm

Przejdź pętlą przez każdy indeks, używając i.
Przejdź pętlą j od i+1 do ostatniego indeksu.
Jeśli numbers[i] + numbers[j] jest równe target, zwróć [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 []

Wyszukiwanie binarne dla każdego partnera

Intuicja

Gdy ustalisz pierwszą wartość numbers[i], dokładnie znasz jej partnera: target - numbers[i]. Część tablicy na prawo od i jest posortowana, więc wyszukiwanie binarne może w O(log n) krokach sprawdzić, czy ten partner się tam znajduje.

Dla [-4, 1, 3, 8, 12] i target = 9: przy i = 0 partnerem byłoby 13, którego brakuje. Przy i = 1 partnerem jest 8, a wyszukiwanie znajduje go pod indeksem 3. Odpowiedź to [1, 3].

Wyszukiwanie tylko na prawo od i zachowuje mniejszy indeks jako pierwszy i zapobiega sparowaniu wartości z samą sobą. Para jest unikalna, więc wartość partnera występuje w tym zakresie co najwyżej raz i każde dopasowanie jest odpowiedzią. Łącznie: n wyszukiwań po O(log n) każde.

Algorytm

Wykonaj pętlę dla i od 0 do n-2.
Oblicz need = target - numbers[i].
Wyszukaj binarnie need w indeksach od i+1 do n-1.
Jeśli znajdziesz go na pozycji mid, zwróć [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 []

Dwa wskaźniki z obu końców

Intuicja

Zacznij od left = 0 i right = n-1, a następnie sprawdź numbers[left] + numbers[right]. Jeśli wynik jest równy target, gotowe. Jeśli jest za mały, numbers[left] nie może być częścią odpowiedzi: nawet w parze z największą wartością, która wciąż jest brana pod uwagę, suma jest za mała. Przesuń więc left w prawo. Jeśli suma jest za duża, numbers[right] również nie może być częścią pary, ponieważ nawet z najmniejszym pozostałym partnerem suma przekracza cel. Przesuń więc right w lewo.

Każdy ruch odrzuca jedną wartość, która nie może należeć do pary, a sama para nigdy nie zostaje odrzucona. Wskaźniki spotykają się po co najwyżej n-1 ruchach, więc przeszukiwanie zajmuje O(n) i wykorzystuje dwie zmienne.

Dla [-4, 1, 3, 8, 12] i target = 9: -4 + 12 = 8 to za mało, więc left przesuwa się na indeks 1. Następnie 1 + 12 = 13 to za dużo, więc right przesuwa się na indeks 3. Teraz 1 + 8 = 9, a odpowiedzią jest [1, 3].

Algorytm

Ustaw left na 0, a right na n-1.
Gdy left < right, oblicz total = numbers[left] + numbers[right].
Jeśli total jest równy target, zwróć [left, right].
Jeśli total jest mniejsze, zwiększ left o 1; jeśli większe, zmniejsz right o 1.

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

Pułapki i przypadki brzegowe

Pętla z dwoma wskaźnikami jest krótka, więc błędy kryją się w szczegółach wokół niej.

Zwracanie pozycji indeksowanych od 1. Ta wersja wymaga indeksów liczonych od 0: dla [-4, 1, 3, 8, 12] i target = 9 odpowiedzią jest [1, 3], a nie [2, 4]. W Lua i R odejmij 1 przed zwróceniem wyniku.
Używanie pętli z warunkiem left <= right. Gdy wskaźniki się spotkają, suma użyje dwukrotnie tej samej wartości.
Przesuwanie niewłaściwego wskaźnika. Zbyt mała suma wymaga większej wartości, a zapewnić ją może tylko left.
Odrzucanie zduplikowanych wartości. Dla [2, 2, 5, 7] i target = 4 używane są obie dwójki, które znajdują się na różnych pozycjach.
Przepełnienie. Podane tu ograniczenia sprawiają, że każda suma mieści się w 32-bitowej liczbie całkowitej. Jeśli wartości mogłyby sięgać 10^9, dodawaj je, używając typu 64-bitowego.

Najczęstsze pytania4

Dlaczego dwa wskaźniki działają w przypadku problemu Two Sum na posortowanej tablicy?

Gdy suma dwóch końców jest zbyt mała, lewa wartość jest zbyt mała dla każdego partnera, który nadal pozostaje w grze, ponieważ prawy koniec jest największy z nich. Możesz ją na stałe odrzucić. Ten sam argument pozwala odrzucić prawą wartość, gdy suma jest zbyt duża. Para będąca odpowiedzią nigdy nie zostaje odrzucona, więc wskaźniki kończą na niej.

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

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) i wymaga O(1) dodatkowej pamięci: w każdym kroku jeden wskaźnik przesuwa się do środka, a wskaźniki spotykają się po co najwyżej n-1 krokach. Wyszukiwanie binarne każdego pasującego elementu zajmuje O(n log n), a sprawdzenie każdej pary zajmuje O(n²).

Dlaczego nie użyć mapy haszującej, tak jak w pierwszym zadaniu Two Sum?

Mapa mieszająca działa i również działa w czasie O(n), ale przechowuje do n wartości. Posortowana kolejność sprawia, że ta pamięć jest zbędna: same wskaźniki wiedzą, w którą stronę się przesunąć, na podstawie samej sumy. Rekruterzy zadają to pytanie, aby sprawdzić, czy korzystasz z podanej kolejności.

Kiedy wyszukiwanie binarne jest tu lepszym wyborem?

Gdy jedna wartość jest ustalona i potrzebujesz tylko jej pary. Jeśli numbers[0] musi znaleźć się w parze, jedno wyszukiwanie binarne znajduje drugi indeks w czasie O(log n). Aby znaleźć nieznaną parę, skanowanie dwoma wskaźnikami jest szybsze niż n oddzielnych wyszukiwań.

Python

def twoSumSorted(numbers, target):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

numbers = [-4, 1, 3, 8, 12]
target = 9

Oczekiwane

[1, 3]

Two Sum II: Sorted Input

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdą parę

Wyszukiwanie binarne dla każdego partnera

Dwa wskaźniki z obu końców

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania