4Sum

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

O(n³). Dwie pętle wybierają około n²/2 par (i, j) , a dla każdej z nich wykonywane jest jedno przejście z użyciem dwóch wskaźników, obejmujące najwyżej n kroków; sortowanie O(n log n) jest niewielkie w porównaniu z tym.

Q: Jak uogólnić 4Sum do kSum?

Zaimplementuj kSum(nums, target, k) dla posortowanej listy. Dla k = 2 funkcja wykonuje przegląd za pomocą dwóch wskaźników. Dla większego k iteruje po pierwszej wartości, pomija powtórzenia i wywołuje samą siebie z k-1 i target - nums[i] dla wartości po prawej stronie. Każdy poziom dodaje czynnik n, więc kSum ma złożoność O(n^(k-1)).

Q: Czy problem 4Sum można rozwiązać w czasie O(n²)?

Możesz pogrupować n²/2 sum par w mapie haszującej i dopasować każdą parę do par o sumie równej target pomniejszonej o jej własną sumę. Jest to szybkie, gdy niewiele par ma tę samą sumę, ale jedna suma może odpowiadać O(n²) parom, więc w najgorszym przypadku złożoność nie jest lepsza niż O(n³).

ŚrednieDwa wskaźniki Sortowanie

+10

Otrzymujesz listę liczb całkowitych nums oraz liczbę całkowitą target. Zwróć wszystkie czwórki [a, b, c, d], których cztery wartości znajdują się na czterech różnych pozycjach w nums i sumują się do target. Zapisz każdą czwórkę w kolejności wartości niemalejącej. Jeśli te same cztery wartości można wybrać z różnych pozycji, czwórka nadal pojawia się tylko raz. Posortuj wynik według pierwszej wartości, następnie drugiej, a potem trzeciej. Jeśli żadna czwórka nie spełnia warunków, zwróć pustą listę.

Funkcja

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: liczby do wyboru, co najmniej jedna
targetinteger: suma, do której musi dojść każda czwórka
Zwracainteger-2d-array: różne czwórki liczb o sumie równej wartości docelowej, każda posortowana, a lista również posortowana; pusta lista, jeśli nie ma żadnych

Ograniczenia

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Suma dowolnych czterech wartości mieści się w przedziale od -4 × 10⁸ do 4 × 10⁸, więc mieści się w 32-bitowej liczbie całkowitej.
Czwórki zawierające te same cztery wartości liczą się jako jedna.

Przykłady

Wejście: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Wyjście: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Wyjaśnienie: Każda z czterech czwórek daje w sumie 1, na przykład -3 + (-1) + 2 + 3. Te dwie, które zaczynają się od -3, są pierwsze i uporządkowane według drugiej wartości: -1 przed 0.

Wejście: nums = [4, 4, 4, 4, 4, 4]target = 16
Wyjście: [[4, 4, 4, 4]]
Wyjaśnienie: Wszystkie 15 możliwości wyboru czterech pozycji spośród sześciu dają cztery 4, które sumują się do 16, więc [4, 4, 4, 4] pojawia się raz.

Wejście: nums = [1, 5, 2, 9]target = 3
Wyjście: []
Wyjaśnienie: Jedynym wyborem są wszystkie cztery liczby, a 1 + 5 + 2 + 9 = 17, a nie 3, więc odpowiedzią jest pusta lista.

Pytanie dodatkowe

Policz zestawy czterech pozycji, których wartości sumują się do target, zamiast różnych czwórek. Drugi przykład zawiera 15 takich zestawów. Czy potrafisz zrobić to w O(n²)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Sprawdzanie każdego zestawu czterech pozycji kosztuje O(n⁴), a powtarzające się wartości wielokrotnie tworzą ten sam poczwórny zestaw. Zastosuj redukcję 3Sum o jeden poziom głębiej: posortuj dane, ustal dwie pierwsze wartości za pomocą dwóch pętli, znajdź ostatnią parę za pomocą dwóch wskaźników i pomijaj powtarzające się wartości na każdym poziomie.

Wypróbuj każdy zestaw czterech

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

Intuicja

Najpierw posortuj liczby, aby pozycje i < j < k < l zawierały wartości w kolejności niemalejącej, a każdy kwartet był zapisany we właściwy sposób. Cztery zagnieżdżone pętle sprawdzają każdą kombinację czterech pozycji. Aby uniknąć powtórzeń, pętla przechodzi dalej, gdy na kolejnej pozycji znajduje się wartość, którą sprawdziła krok wcześniej. W przypadku sześciu czwórek każda pętla sprawdza tylko pierwszą pozycję, więc [4, 4, 4, 4] pojawia się raz zamiast 15 razy.

Dla 200 liczb istnieje 64,684,950 zestawów po cztery, a ich liczba rośnie około 16 razy, gdy n się podwaja.

Algorytm

Posortuj nums.
Zagnieźdź cztery pętle obejmujące i < j < k < l, z których każda zaczyna się o jeden indeks dalej niż otaczająca ją pętla.
W każdej pętli pomiń pozycję, która nie jest pierwszą pozycją tej pętli i ma taką samą wartość jak poprzednia pozycja.
Zapisz [nums[i], nums[j], nums[k], nums[l]], gdy suma tych czterech wartości wynosi target. Pętle generują je w posortowanej kolejności.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Sortowanie, dwie pętle, dwa wskaźniki

Intuicja

Ustal nums[i] i nums[j], a pozostaje problem znalezienia pary: znajdź dwie wartości na prawo od j, których suma wynosi target - nums[i] - nums[j]. W posortowanej liście wystarczy jedno przejście. Ustaw lo na j+1, a hi na ostatnim indeksie. Suma mniejsza od target przesuwa lo w prawo; suma większa od niego przesuwa hi w lewo.

Każdy ruch odrzuca wartość, która nie należy do żadnego rozwiązania. Jeśli suma jest za mała, nawet największa pozostała wartość, nums[hi], nie wystarczy dla nums[lo], więc można odrzucić nums[lo]. Suma, która jest za duża, z analogicznego powodu pozwala odrzucić nums[hi]. Jedna para (i, j) wymaga najwyżej n ruchów, więc n²/2 par ma łączny koszt O(n³).

W pierwszym przykładzie, gdy i wskazuje -3, a j wskazuje -1, lo przesuwa się z 0, mija 1 i dochodzi do 2, gdzie -3 + (-1) + 2 + 3 = 1.

Algorytm

Posortuj nums.
Dla każdego i pomiń go, gdy i > 0 i nums[i] jest równe nums[i-1].
Dla każdego j po i pomiń go, gdy j > i+1 i nums[j] jest równe nums[j-1].
Ustaw lo = j+1 i hi = n-1. Dopóki lo < hi, porównuj sumę czterech wartości z target: jeśli jest mniejsza, przesuń lo w prawo, a jeśli większa — przesuń hi w lewo.
Gdy znajdziesz dopasowanie, zapisz czwórkę, przesuń oba wskaźniki, a następnie przesuwaj lo dalej, dopóki wskazuje wartość, której właśnie użyto.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Pułapki i przypadki brzegowe

Pomijanie j, gdy nums[j] jest równe nums[j-1]. Przy j = i+1 porównywana jest wartość używana przez i, więc dla [2, 2, 2, 2, 2] i targetu 8 zostaje pominięte [2, 2, 2, 2].
Skopiowanie wczesnego zakończenia z 3Sum: nums[i] > target. Dla [-5, -4, -3, -2, -1] i targetu -10 pętla zatrzymuje się przy -5 i pomija [-4, -3, -2, -1].
Listy krótsze niż cztery elementy. Przy jednej lub dwóch liczbach n-3 jest ujemne: 0..<(n - 3) powoduje pułapkę w Swift, a n - 3 dla usize w Rust powoduje niedomiar. Najpierw zwróć pustą listę.
Zbieranie czwórek w zbiorze haszującym i zwracanie ich bez sortowania.

Najczęstsze pytania3

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

O(n³). Dwie pętle wybierają około n²/2 par (i, j), a dla każdej z nich wykonywane jest jedno przejście z użyciem dwóch wskaźników, obejmujące najwyżej n kroków; sortowanie O(n log n) jest niewielkie w porównaniu z tym.

Jak uogólnić 4Sum do kSum?

Zaimplementuj kSum(nums, target, k) dla posortowanej listy. Dla k = 2 funkcja wykonuje przegląd za pomocą dwóch wskaźników. Dla większego k iteruje po pierwszej wartości, pomija powtórzenia i wywołuje samą siebie z k-1 i target - nums[i] dla wartości po prawej stronie. Każdy poziom dodaje czynnik n, więc kSum ma złożoność O(n^(k-1)).

Czy problem 4Sum można rozwiązać w czasie O(n²)?

Możesz pogrupować n²/2 sum par w mapie haszującej i dopasować każdą parę do par o sumie równej target pomniejszonej o jej własną sumę. Jest to szybkie, gdy niewiele par ma tę samą sumę, ale jedna suma może odpowiadać O(n²) parom, więc w najgorszym przypadku złożoność nie jest lepsza niż O(n³).

def fourSum(nums, target):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

nums = [3, -1, 0, 2, -2, 1, -3]
target = 1

Oczekiwany wynik

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]