Longest Subarray with Sum K

+10

Dla tablicy liczb całkowitych nums i wartości docelowej k zwróć długość najdłuższej podtablicy, której elementy sumują się dokładnie do k. Podtablica to ciąg kolejnych elementów o długości co najmniej jeden. Niektóre wartości mogą być równe zero lub mniejsze od zera. Jeśli żadna podtablica nie sumuje się do k, zwróć 0.

Funkcja

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

numsinteger-array: liczby całkowite do wyszukania, w tym liczby ujemne i zera
kinteger: dokładna suma, jaką musi mieć podtablica
Zwracainteger: długość najdłuższej podtablicy, której suma wynosi k, lub 0, jeśli taka nie istnieje

Ograniczenia

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Każda suma prefiksowa mieści się w zakresie od -2 × 10⁸ do 2 × 10⁸, więc wystarczą liczby całkowite 32-bitowe.
Zwróć 0, gdy żadna podtablica nie sumuje się do k.

Przykłady

Wejście: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Wyjście: 5
Wyjaśnienie: Trzy ciągi dają w sumie 5: [2, 3] na końcu, [2, -1, 3, 1] na początku oraz [3, 1, -4, 2, 3] na indeksach od 2 do 6. Ostatni jest najdłuższy i zawiera 5 elementów.

Wejście: nums = [4, 1, 1, 2, -1, 1]k = 3
Wyjście: 4
Wyjaśnienie: [1, 1, 2, -1] na indeksach od 1 do 4 oraz [1, 2, -1, 1] na indeksach od 2 do 5 sumują się do 3 i zawierają po 4 elementy. Zwracasz długość, więc remis nie ma znaczenia.

Pytanie dodatkowe

Jak znaleźć najdłuższą podtablicę, której suma jest nie większa niż k, przy czym wartości ujemne są nadal dozwolone?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Sumy skumulowane sprowadzają sumę dowolnej podtablicy do jednego odejmowania: elementy po indeksie s aż do indeksu i dają w sumie prefix[i] - prefix[s]. Zapamiętaj pierwszy indeks, pod którym pojawia się każda suma, a jedno przejście znajdzie najdłuższe dopasowanie kończące się na każdej pozycji.

Rozwijaj każdą podtablicę od każdego początku

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

Intuicja

Z każdego początku rozszerzaj zakres w prawo i dodawaj każdy element do bieżącej sumy. Za każdym razem, gdy suma jest równa k, zapisz długość. Każda podtablica odpowiada jednej parze początku i końca, więc żadna nie zostanie pominięta. Rozszerzaj zakres dalej, nawet gdy suma przekroczy k: od indeksu 2 w pierwszym przykładzie sumy wynoszą 3, 4, 0, 2, 5, a to dzięki -4 ostatnia osiąga 5.

Istnieje około n²/2 par: 2 × 10^8 dodawań dla n = 2 × 10^4.

Algorytm

Ustaw best na 0.
Dla każdego start ustaw total na 0.
Przesuwaj end od start do ostatniego indeksu i dodawaj nums[end] do total.
Gdy total jest równe k, ustaw best na większą z wartości best i end - start + 1.
Zwróć best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Sumy prefiksowe z pierwszym indeksem każdej sumy

Intuicja

Przedział kończący się na indeksie i sumuje się do k dokładnie wtedy, gdy wcześniejsza suma jest równa prefix - k. Jeśli kwalifikuje się kilka wcześniejszych sum, pierwsza z nich rozpoczyna najdłuższy przedział, dlatego mapa przechowuje każdą sumę tylko przy jej pierwszym wystąpieniu. Późniejsza kopia mogłaby rozpocząć jedynie krótszy przedział. Zainicjuj mapę sumą 0 na indeksie -1, aby dopasowanie rozpoczynające się na indeksie 0 miało długość i + 1.

W pierwszym przykładzie sumy wynoszą 2, 1, 4, 5, 1, 3, 6. Na indeksie 6 wartość 6 - 5 = 1 pojawiła się po raz pierwszy na indeksie 1, co daje długość 5. Suma 1 pojawia się ponownie na indeksie 4, a zachowanie indeksu 1 pozwala znaleźć ten przedział.

Jedno wyszukiwanie na element daje czas O(n), a mapa przechowuje najwyżej n + 1 sum.

Algorytm

Utwórz mapę first, przechowującą sumę 0 pod indeksem -1, i ustaw prefix oraz best na 0.
Dla każdego indeksu i dodaj nums[i] do prefix.
Jeśli prefix - k znajduje się w mapie pod indeksem start, ustaw best na większą z wartości best i i - start.
Jeśli prefix nie ma jeszcze w mapie, zapisz go pod indeksem i.
Zwróć best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Pułapki i przypadki brzegowe

Nadpisywanie za każdym razem zapisanego indeksu, gdy suma częściowa się powtarza, zachowuje najnowszy początek i pozwala znaleźć krótszy pasujący fragment. Pierwszy przykład zwraca 4 zamiast 5, ponieważ suma częściowa 1 przenosi się z indeksu 1 na indeks 4.
Okno, które się zmniejsza, gdy jego suma jest większa niż k, również zwraca 4 w pierwszym przykładzie. Kończy, zawierając [-1, 3, 1, -4, 2, 3], z sumą 4, i nigdy nie usuwa -1.
Pominięcie sumy częściowej 0 na indeksie -1 powoduje pominięcie każdego pasującego fragmentu zaczynającego się na indeksie 0: [5, 0, 0, 0] przy k = 5 zwraca 0 zamiast 4.
Zapisany indeks to pozycja przed podtablicą, więc jej długość wynosi i - start. Dodanie 1 powoduje policzenie o jednego elementu za dużo.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu najdłuższego podciągu o sumie K?

Czas O(n) i dodatkowa pamięć O(n) dzięki sumom narastającym i mapie pierwszych indeksów: jedno wyszukanie i najwyżej jedno wstawienie na element. Rozwijanie każdego podciągu od każdego początku kosztuje O(n²) czasu i O(1) pamięci.

Dlaczego metoda okna przesuwnego zawodzi, gdy tablica zawiera liczby ujemne?

Metoda przesuwnego okna zakłada, że dodanie elementu zwiększa sumę, a usunięcie jej zmniejsza. Przy wartościach ujemnych okno, którego suma jest zbyt duża, może nadal osiągnąć k, gdy pojawi się element ujemny, a okno, którego suma jest zbyt mała, może wymagać usunięcia ujemnego elementu z lewej strony. Okno nie jest w stanie określić, który ruch jest właściwy.

Czy problem znalezienia najdłuższej podtablicy o sumie K można rozwiązać przy użyciu O(1) dodatkowej pamięci?

Tylko wtedy, gdy żadna wartość nie jest ujemna. Wówczas suma nigdy nie maleje wraz ze zwiększaniem okna, a dwa wskaźniki znajdują najdłuższe okno o sumie k w czasie O(n) i przy użyciu O(1) pamięci. W przypadku wartości ujemnych potrzebujesz mapy sum albo skanowania O(n²).

def longestSubarrayWithSumK(nums, k):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Oczekiwany wynik