Minimum Size Subarray Sum

Q: Jaka jest złożoność czasowa problemu „Minimum Size Subarray Sum”?

Rozwiązanie z użyciem przesuwanego okna działa w czasie O(n) i zajmuje O(1) pamięci. Pętla wewnętrzna może sprawiać wrażenie, że złożoność wynosiłaby O kwadratowe, ale left przesuwa się tylko do przodu, więc w całym przebiegu przesuwa się najwyżej n razy. Wersja z sumą prefiksową ma złożoność O(n log n) , a sprawdzanie każdego początku ma złożoność O(n²) .

Q: Po co uczyć się rozwiązania z sumami prefiksowymi o złożoności O(n log n), skoro istnieje rozwiązanie O(n)?

Rekruterzy często pytają o to po odpowiedzi O(n) . Pokazuje to inne zastosowanie wartości dodatnich: sumy prefiksowe są posortowane, więc wyszukiwanie binarne pozwala znaleźć miejsce, w którym suma bieżąca po raz pierwszy przekracza próg. To narzędzie przydaje się w innych zadaniach, takich jak losowanie indeksu z prawdopodobieństwem proporcjonalnym do jego wagi.

Q: Czy suma elementów podtablicy musi być równa dokładnie wartości docelowej?

Nie. Liczy się każda suma większa lub równa target . Przy target = 15 okno 9, 3, 7 daje w sumie 19 i nadal ma długość 3. Jeśli potrzebujesz dokładnej sumy, okno nadal działa dla wartości dodatnich: zmniejszaj je, gdy suma przekracza wartość docelową, i zapisuj długość tylko wtedy, gdy suma jest jej równa.

ŚredniePrzesuwane okno Sumy prefiksowe

+10

Otrzymujesz dodatnią liczbę całkowitą target oraz tablicę nums zawierającą dodatnie liczby całkowite. Znajdź najkrótszą podtablicę (ciąg sąsiadujących elementów), której suma jest co najmniej równa target, i zwróć jej długość. Jeśli żadna podtablica nie osiąga wartości target, zwróć 0.

Funkcja

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

targetinteger: suma, którą podtablica musi osiągnąć lub przekroczyć
numsinteger-array: tablica liczb całkowitych dodatnich
Zwracainteger: długość najkrótszej podtablicy, której suma wynosi co najmniej target, lub 0, jeśli taka nie istnieje

Ograniczenia

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Przykłady

Wejście: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Wyjście: 3
Wyjaśnienie: Żadni dwaj sąsiedzi nie osiągają 15: największa para to 9 + 3 = 12. Trzy liczby osiągają ten wynik: 4 + 2 + 9 = 15 oraz 9 + 3 + 7 = 19, więc odpowiedź to 3.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak rozwiążesz ten problem, jeśli nums może zawierać również zera i liczby ujemne, przez co metoda przesuwanego okna przestaje działać?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Wszystkie wartości są dodatnie, więc wydłużenie podtablicy zawsze zwiększa jej sumę, a jej skrócenie zawsze ją zmniejsza. Ten jeden fakt stanowi podstawę obu szybkich rozwiązań. Sumy prefiksowe tworzą posortowaną listę, więc wyszukiwanie binarne znajduje miejsce, w którym suma po raz pierwszy osiąga wartość target. Co więcej, najlepszy koniec nigdy nie przesuwa się w lewo, gdy początek przesuwa się w prawo, więc jedno okno, które rozszerza się z prawej i zwęża z lewej, znajduje odpowiedź w jednym przebiegu.

Rozszerzaj od każdego początku

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

Intuicja

Ustal indeks początkowy i dodawaj wartości po kolei, przesuwając się w prawo. Gdy suma bieżąca po raz pierwszy osiągnie target, otrzymujesz najkrótszą podtablicę zaczynającą się od tego indeksu: każda krótsza kończyła się wcześniej, a jej suma była wciąż za mała. Zapisz więc jej długość, przestań dodawać kolejne elementy i przejdź do następnego indeksu początkowego. Odpowiedzią jest najmniejsza długość spośród wszystkich indeksów początkowych.

Dla target = 15 i [4, 2, 9, 3, 7, 1, 5] sumy dla indeksu początkowego 0 wynoszą 4, 6, 15, więc kończymy na długości 3. Dla indeksu 1 sumy wynoszą 2, 11, 14, 21, więc kończymy na długości 4. Dla indeksu 2 sumy wynoszą 9, 12, 19, czyli znów długość wynosi 3. Żaden indeks początkowy nie daje lepszego wyniku niż 3.

Problem pojawia się, gdy trudno osiągnąć wartość docelową. Jeśli żadna podtablica jej nie osiągnie, każdy indeks początkowy będzie sprawdzany aż do końca tablicy: n(n+1)/2 dodawań, czyli 2 × 10^8 dla n = 2 × 10^4. Dla każdego indeksu początkowego ponownie obliczane są też sumy, które zostały już obliczone dla poprzedniego indeksu.

Algorytm

Ustaw best na 0, co oznacza, że jeszcze niczego nie znaleziono.
Dla każdego indeksu początkowego ustaw bieżącą sumę na 0.
Przesuwaj indeks końcowy w prawo od indeksu początkowego, dodając nums[end] do sumy.
Gdy suma osiągnie target, zachowaj end-start+1, jeśli jest większe niż best, i przestań rozszerzać zakres od tego indeksu początkowego.
Zwróć best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Sumy prefiksowe i wyszukiwanie binarne

Intuicja

Niech prefix[k] oznacza sumę pierwszych k wartości, przy czym prefix[0] = 0. Suma nums[start..end-1] wynosi zatem prefix[end] - prefix[start]. Dla ustalonego początku szukasz najmniejszego end, dla którego prefix[end] ≥ prefix[start] + target.

Każda wartość jest dodatnia, więc prefix jest ściśle rosnące, a znalezienie pierwszej pozycji, na której osiąga daną wartość, wymaga wyszukiwania binarnego. Dla [4, 2, 9, 3, 7, 1, 5] prefix wynosi [0, 4, 6, 15, 18, 25, 26, 31]. Dla początku 2 potrzebujesz 6 + 15 = 21; pierwsza wartość w prefix wynosząca co najmniej 21 to 25 na indeksie 5, więc okno to nums[2..4] = 9, 3, 7, o długości 3.

Jeśli nawet prefix[n] jest mniejsze od wartości wymaganej dla danego początku, żadne end nie będzie dla niego odpowiednie, a żadne nie będzie odpowiednie również dla żadnego późniejszego początku, ponieważ prefix[start] tylko rośnie. Zakończ w tym miejscu. To daje n wyszukiwań binarnych, czas O(n log n) oraz dodatkowo O(n) na tablicę sum prefiksowych. Największa porównywana wartość to 2 × 10^8 + 10^9, co mieści się w 32-bitowej liczbie całkowitej.

Algorytm

Zbuduj tablicę prefix o długości n+1, gdzie prefix[k+1] = prefix[k] + nums[k].
Dla każdego początku oblicz need = prefix[start] + target.
Jeśli prefix[n] < need, zakończ: żaden późniejszy początek nie da wyniku.
Wyszukiwaniem binarnym znajdź na pozycjach od start+1 do n pierwsze end, dla którego prefix[end] ≥ need, i zachowaj end-start, jeśli jest to dotychczas najkrótszy wynik.
Zwróć najkrótszą długość albo 0, jeśli żaden początek nie dał wyniku.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Przesuwne okno

Intuicja

Utrzymuj okno nums[left..right] i jego sumę. Przesuwaj right o jeden krok i dodawaj nową wartość. Gdy suma jest co najmniej równa target, okno jest kandydatem: zapisz jego długość, a następnie usuń nums[left] i przesuń left do przodu, aby sprawdzić, czy krótsze okno nadal spełnia warunek.

Dlaczego left może już na stałe opuścić okno? Gdy okno nums[left..right] po raz pierwszy osiąga target, mniejsze okno nums[left..right-1] tego nie zrobiło, ponieważ pętla zmniejszyłaby je w poprzednim kroku. Zatem right jest najwcześniejszym końcem dla tego początku, a każdy późniejszy koniec daje tylko dłuższą podtablicę. Ten początek dał już najlepszą odpowiedź. To rozumowanie wymaga dodatnich wartości: przy liczbie ujemnej dłuższe okno mogłoby później mieć większą sumę.

Dla target = 15 i [4, 2, 9, 3, 7, 1, 5]: suma rośnie kolejno do 4, 6, 15, więc zapisywana jest długość 3, a 4 opuszcza okno (11). Dodanie 3 daje 14, a dodanie 7 daje 21: zapisz długość 4, usuń 2 (19), zapisz długość 3, usuń 9 (10). Dodanie 1 i 5 daje 16: zapisz długość 4, usuń 3 (13). Odpowiedź to 3.

Pętla while znajduje się wewnątrz pętli for, ale każdy indeks wchodzi do okna raz i raz je opuszcza, więc całkowita złożoność czasowa wynosi O(n). Przechowywane są tylko trzy liczby, więc złożoność pamięciowa wynosi O(1).

Algorytm

Ustaw left = 0, total = 0 i best = 0.
Dla każdego right dodaj nums[right] do total.
Gdy total ≥ target, zachowaj right-left+1, jeśli jest większe niż best, odejmij nums[left] i przesuń left o jeden krok w prawo.
Zwróć best, które nadal wynosi 0, jeśli suma nigdy nie osiągnęła target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Pułapki i przypadki brzegowe

Większość błędów pojawia się na etapie zmniejszania okna oraz przy wartości zwracanej, gdy nic nie osiąga target.

Zmniejszanie okna za pomocą if zamiast while. Dla target = 12 i [1, 1, 2, 3, 12] dodanie 12 daje sumę 19. Instrukcja if zapisuje długość 5, usuwa jedną wartość i przechodzi dalej, więc okno [12] o długości 1 nigdy nie zostaje zmierzone. Pętla usuwa kolejne wartości, dopóki suma jest wystarczająca.
Zapisywanie długości po usunięciu nums[left] zamiast przed nim. Mierzone okno musi być tym, którego suma osiągnęła target.
Porównywanie za pomocą > zamiast ≥. Podtablica, której suma jest równa target, również się liczy: [3, 3, 3] przy target = 9 ma odpowiedź 3, a nie 0.
Zwracanie wartości wartowniczej. Jeśli ustawisz początkowo best na n+1 lub nieskończoność, zamień ją na 0, gdy nic nie osiągnęło target.
Ponowne używanie okna w tablicach zawierających zera lub liczby ujemne. Metoda zakłada, że każda wartość jest dodatnia; ten problem to gwarantuje, ale jego warianty już nie.

Najczęstsze pytania4

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

Rozwiązanie z użyciem przesuwanego okna działa w czasie O(n) i zajmuje O(1) pamięci. Pętla wewnętrzna może sprawiać wrażenie, że złożoność wynosiłaby O kwadratowe, ale left przesuwa się tylko do przodu, więc w całym przebiegu przesuwa się najwyżej n razy. Wersja z sumą prefiksową ma złożoność O(n log n), a sprawdzanie każdego początku ma złożoność O(n²).

Dlaczego metoda przesuwnego okna wymaga liczb dodatnich?

Zmniejszenie okna musi obniżać jego sumę, a zwiększenie go musi ją podwyższać, w przeciwnym razie usunięcie lewego elementu mogłoby odrzucić początek odpowiedzi. W przypadku liczb ujemnych ta zależność przestaje działać. Typowym rozwiązaniem są sumy prefiksowe i monotoniczna kolejka dwustronna z kandydatami na początek, która nadal działa w O(n).

Po co uczyć się rozwiązania z sumami prefiksowymi o złożoności O(n log n), skoro istnieje rozwiązanie O(n)?

Rekruterzy często pytają o to po odpowiedzi O(n). Pokazuje to inne zastosowanie wartości dodatnich: sumy prefiksowe są posortowane, więc wyszukiwanie binarne pozwala znaleźć miejsce, w którym suma bieżąca po raz pierwszy przekracza próg. To narzędzie przydaje się w innych zadaniach, takich jak losowanie indeksu z prawdopodobieństwem proporcjonalnym do jego wagi.

Czy suma elementów podtablicy musi być równa dokładnie wartości docelowej?

Nie. Liczy się każda suma większa lub równa target. Przy target = 15 okno 9, 3, 7 daje w sumie 19 i nadal ma długość 3. Jeśli potrzebujesz dokładnej sumy, okno nadal działa dla wartości dodatnich: zmniejszaj je, gdy suma przekracza wartość docelową, i zapisuj długość tylko wtedy, gdy suma jest jej równa.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Oczekiwane

Minimum Size Subarray Sum

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rozszerzaj od każdego początku

Sumy prefiksowe i wyszukiwanie binarne

Przesuwne okno

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania