Subarray Sum Equals K

+10

Otrzymujesz tablicę liczb całkowitych nums i liczbę całkowitą k. Policz podtablice, których elementy sumują się dokładnie do k. Podtablica to ciąg jednego lub większej liczby sąsiadujących elementów. Dwie podtablice liczą się osobno, gdy zaczynają się lub kończą na różnych pozycjach, nawet jeśli zawierają te same wartości. Wartości mogą być ujemne lub równe zero.

Funkcja

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: tablica liczb całkowitych, która może zawierać wartości ujemne i zera
kinteger: suma, jaką musi osiągnąć podtablica, aby została zaliczona
Zwracainteger: liczba podtablic, których elementy sumują się do k

Ograniczenia

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Tablica tej długości ma co najwyżej 200,010,000 podtablic, więc wynik mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Wyjście: 4
Wyjaśnienie: Cztery serie dają łącznie 7: [3, 4], [1, 3, 3], [3, 3, 1] i [3, 4, -7, 1, 3, 3]. W ostatniej z nich -7 równoważy 3 i 4, a suma później znów rośnie do 7, więc seria może pasować nawet wtedy, gdy jej suma przekroczyła k.

Wejście: nums = [1, -1, 0]k = 0
Wyjście: 3
Wyjaśnienie: Trzy podtablice sumują się do 0: [1, -1], [0] oraz cała tablica [1, -1, 0]. Fragment [-1, 0] sumuje się do -1, więc się nie liczy.

Wejście: nums = [2, 2, 2]k = 4
Wyjście: 2
Wyjaśnienie: Seria [2, 2] na indeksach 0 i 1 oraz seria [2, 2] na indeksach 1 i 2 zawierają te same wartości, ale znajdują się na różnych pozycjach, więc obie są liczone. Suma całej tablicy wynosi 6.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak zmieniłbyś rozwiązanie, aby zwracało długość najdłuższej podtablicy, której suma wynosi k, nadal w czasie O(n)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Tablica n liczb ma n(n+1)/2 podtablic, czyli około 2 × 10^8, gdy n = 2 × 10^4, więc sumowanie każdej z nich jest zbyt wolne. Ujemne wartości wykluczają też użycie okna przesuwnego: suma w oknie może maleć, a potem znów rosnąć, więc nie ma reguły, która podpowiadałaby, kiedy je zmniejszyć. Pomysł, który rozwiązuje ten problem, polega na zapisaniu sumy każdej podtablicy jako różnicy dwóch sum prefiksowych. Zliczenie podtablic kończących się na bieżącym elemencie, których suma wynosi k, sprowadza się wtedy do zliczenia wcześniejszych sum prefiksowych równych bieżącej sumie pomniejszonej o k, a mapa haszująca pozwala zrobić to w jednym przebiegu.

Każde rozpoczęcie z sumą bieżącą

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

Intuicja

Każda podtablica ma pierwszy indeks start i ostatni indeks end. Jeśli odwiedzisz każdą parę i sprawdzisz jej sumę, uwzględnisz każdą podtablicę dokładnie raz, więc liczba będzie prawidłowa.

Nie potrzebujesz trzeciej pętli, aby zsumować elementy każdej podtablicy. Ustal start, a następnie przesuwaj end w prawo o jeden krok i dodawaj nums[end] do bieżącej wartości total. Suma zawsze zawiera sumę elementów od start do end, więc dla każdej podtablicy potrzeba jednego dodawania i jednego porównania.

Nie zatrzymuj się, gdy suma osiągnie wartość k lub ją przekroczy. Późniejsza wartość ujemna może ją obniżyć: w pierwszym przykładzie suma zaczynając od indeksu 0 wynosi kolejno 3, 7, 0, 1, 4, 7, więc dla tego początku drugie dopasowanie pojawia się przy indeksie 5.

Koszt zależy od liczby par. Dla n = 2 × 10^4 jest ich około 2 × 10^8, co jest w porządku w C, ale zdecydowanie za wolne w Pythonie, Ruby lub R.

Algorytm

Ustaw count na 0.
Dla każdego start od 0 do n-1 ustaw total na 0.
Dla każdego end od start do n-1 dodaj nums[end] do total.
Jeśli total jest równe k, dodaj 1 do count i kontynuuj w obu przypadkach.
Zwróć count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Sumy prefiksowe z mapą liczności

Intuicja

Niech prefix[j] będzie sumą pierwszych j elementów, przy czym prefix[0] = 0 dla pustego prefiksu. Suma podtablicy od indeksu i do indeksu j-1 wynosi prefix[j] - prefix[i]. Zatem suma podtablicy kończącej się na bieżącym elemencie jest równa k dokładnie wtedy, gdy wcześniejsza suma prefiksowa jest równa bieżącej sumie prefiksowej pomniejszonej o k. Każdy taki wcześniejszy prefiks wskazuje początek jednej pasującej podtablicy.

Przejdź przez tablicę jeden raz. Zachowuj bieżącą sumę prefiksową oraz mapę haszującą seen, która dla każdej sumy prefiksowej przechowuje liczbę jej wystąpień. Dla każdego elementu najpierw dodaj seen[prefix - k] do licznika, a następnie zapisz bieżący prefiks. Wyszukiwanie przed zapisaniem zapobiega powstaniu pustej podtablicy: przy k = 0 wcześniejszy zapis dopasowałby bieżący prefiks do samego siebie.

Weźmy pierwszy przykład, w którym k = 7. Sumy prefiksowe to 0, 3, 7, 0, 1, 4, 7, 8, 4. Gdy suma prefiksowa osiąga 7 po indeksie 1, mapa zawiera jedno 0, co daje [3, 4]. Gdy ponownie osiąga 7 po indeksie 5, mapa zawiera dwa zera: pusty prefiks i prefiks po wartości -7. Dają one jednocześnie [3, 4, -7, 1, 3, 3] oraz [1, 3, 3]. Przy wartości 8 po indeksie 6 mapa zawiera jedną 1, co daje [3, 3, 1]. Łącznie daje to 4.

Rozpoczęcie od mapy, w której 0 występuje raz, pozwala zliczać podtablice zaczynające się od indeksu 0. Mapa liczników zamiast zbioru ma znaczenie, ponieważ ta sama suma prefiksowa może się powtarzać, a każde jej wystąpienie rozpoczyna inną podtablicę. Dla każdego elementu wykonywane jest jedno wyszukiwanie i jedna aktualizacja, więc czas działania wynosi O(n), a mapa przechowuje najwyżej n+1 kluczy.

Algorytm

Utwórz mapę seen z seen[0] = 1 i ustaw prefix oraz count na 0.
Dla każdego elementu dodaj go do prefix.
Dodaj seen[prefix - k] do count, odczytując brakujący klucz jako 0.
Dodaj 1 do seen[prefix].
Zwróć count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z traktowania danych wejściowych tak, jakby każda wartość była dodatnia, albo z niewłaściwej kolejności dwóch operacji na mapie.

Przesuwne okno, które się kurczy, gdy suma przekroczy k, nie działa dla wartości ujemnych. W pierwszym przykładzie zwraca 2 zamiast 4: okno pozostawia lewy brzeg na indeksie 0, aż suma przekroczy 7 na indeksie 6, więc nigdy nie sprawdza [1, 3, 3] ani [3, 3, 1].
Pominięcie seen[0] = 1 powoduje nieuwzględnienie każdej podtablicy zaczynającej się na indeksie 0. Dla nums = [5] i k = 5 zwraca 0 zamiast 1.
Zapisanie bieżącego prefiksu przed wyszukiwaniem powoduje zliczanie pustych podtablic, gdy k wynosi 0. Dla [1, -1, 0] zwraca 6 zamiast 3.
Zbiór sum prefiksów zamiast mapy zliczeń powoduje zaniżanie wyniku, gdy wartości się powtarzają. Dla [0, 0, 0] i k = 0 odpowiedź wynosi 6, ponieważ każda wcześniejsza kopia tej samej sumy prefiksu rozpoczyna inną podtablicę.
W rozwiązaniu siłowym przerwanie pętli wewnętrznej, gdy suma przekroczy k, jest błędne z tego samego powodu co w przypadku przesuwnego okna.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu „Subarray Sum Equals K”?

Rozwiązanie wykorzystujące sumy prefiksowe i mapę haszującą działa w czasie O(n) i wymaga O(n) dodatkowej pamięci: jednego przejścia, z jednym wyszukiwaniem i jedną aktualizacją dla każdego elementu. Sprawdzanie każdego podciągu za pomocą sumy bieżącej zajmuje czas O(n²), a sumowanie każdego podciągu od początku zajmuje czas O(n³).

Dlaczego metoda przesuwnego okna nie działa w przypadku problemu sumy podtablicy równej K?

Metoda przesuwnego okna opiera się na tym, że suma rośnie, gdy okno się powiększa, i maleje, gdy się zmniejsza, co zachodzi tylko wtedy, gdy każda wartość jest dodatnia. Przy wartościach ujemnych okno, którego suma jest już zbyt duża, może stać się dopasowaniem po dalszym powiększeniu, więc żadna reguła nie podpowiada, kiedy przesunąć lewą krawędź. Gdyby każda wartość była dodatnia, metoda przesuwnego okna rozwiązałaby to w czasie O(n) i przy użyciu O(1) pamięci.

Dlaczego mapa haszująca zaczyna się od przypisania 0 do 1?

Ten wpis oznacza pusty prefiks przed pierwszym elementem, którego suma wynosi 0. Suma podtablicy zaczynającej się od indeksu 0 jest równa bieżącej sumie prefiksowej pomniejszonej o sumę tego pustego prefiksu, więc bez tego wpisu takie podtablice nigdy nie są zliczane. Dla nums = [5] i k = 5 wyszukanie 5 - 5 = 0 znajduje ten wpis i zwraca 1.

Czy problem sumy podtablicy równej K można rozwiązać przy użyciu O(1) dodatkowej pamięci?

Nie za pomocą metody jednokrotnego przejścia. Aby policzyć dopasowania kończące się na danym elemencie, musisz wiedzieć, które sumy prefiksowe wystąpiły przed nim, a może ich być nawet n+1 różnych. Bez mapy wracasz do sumy narastającej o złożoności O(n²). Gdy każda wartość jest dodatnia, metoda przesuwnego okna pozwala policzyć podtablice w czasie O(n) i przy użyciu O(1) pamięci.

Python

def subarraySum(nums, k):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Oczekiwane