Zliczanie podtablic o zadanej sumie
Łączenie sum prefiksowych z tablicą haszującą
Zliczanie podtablic o zadanej sumie to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Trudniejsze pytanie
Pora na utrudnienie: należy policzyć, ile podtablic ma sumę równą wartości docelowej k. Sprawdzanie każdej pary jest powolne, ale sumy prefiksowe oraz mapa haszująca pozwalają rozwiązać ten problem. 🎯
Nowe spojrzenie dzięki sumom prefiksowym
Suma podtablicy jest równa prefix[r + 1] minus prefix[l]. Zatem suma równa k oznacza, że dwie wartości prefiksowe różnią się dokładnie o k.
Kluczowe przekształcenie
Jeśli bieżąca suma prefiksowa wynosi P, potrzebna jest wcześniejsza suma prefiksowa równa P minus k. To przekształcenie stanowi całą sztuczkę.
need = current_prefix - kNależy liczyć, a nie wyszukiwać
Zamiast za każdym razem przeszukiwać wcześniejsze elementy, należy zapamiętywać, ile razy pojawiła się każda wartość sumy prefiksowej. Bieżący licznik udziela odpowiedzi w czasie O(1).
Użycie mapy częstości
Słownik przypisuje każdej wartości sumy prefiksowej liczbę jej wystąpień. Ta mapa zamienia wyszukiwanie w natychmiastowe zliczanie.
from collections import defaultdict
seen = defaultdict(int)Zainicjowanie pustej sumy prefiksowej
Przed rozpoczęciem pętli należy zapisać, że suma prefiksowa 0 wystąpiła raz. To zainicjowanie pozwala zliczać podtablice zaczynające się od indeksu 0.
seen[0] = 1Pętla wykonująca jedno przejście
Dla każdego elementu należy zaktualizować bieżącą sumę prefiksową, dodać liczbę wystąpień potrzebnej wartości, a następnie zapisać bieżącą sumę prefiksową. Jedno przejście wystarczy do wykonania całości.
total += x
count += seen[total - k]
seen[total] += 1Dlaczego kolejność ma znaczenie
Najpierw należy dodać wartość do wyniku, a dopiero potem zapisać bieżącą sumę prefiksową. W przeciwnym razie pojawi się przedział o długości zero i zliczanie będzie niepoprawne.
Zysk na szybkości
Przetwarzanie każdego elementu wymaga stałej ilości pracy, więc całe zliczanie działa w czasie O(n). Dla dużych danych jest to lepsze niż metoda brutalna o złożoności O(n kwadrat).
Liczby ujemne nie stanowią problemu
W przeciwieństwie do okien przesuwnych ta metoda bez problemu obsługuje liczby ujemne, ponieważ różnice sum prefiksowych pozostają poprawne niezależnie od znaków.
Klasyczny przypadek użycia
Ten schemat rozwiązuje słynny problem sumy podtablicy równej k oraz wiele jego zamaskowanych wariantów w systemach sprawdzających zadania konkursowe.
Szybki sprawdzian
Bieżąca suma prefiksowa wynosi P, a wartość docelowa to k.
Podsumowanie
Można zliczać podtablice o docelowej sumie w czasie O(n), używając sum prefiksowych i mapy częstości. Należy zainicjować sumę prefiksową 0, a następnie zliczać przed zapisaniem bieżącej wartości. ✅
Często zadawane pytania
Czy lekcja „Zliczanie podtablic o zadanej sumie” jest bezpłatna?
Tak — pełny tekst „Zliczanie podtablic o zadanej sumie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Zliczanie podtablic o zadanej sumie”?
Łączenie sum prefiksowych z tablicą haszującą Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Zliczanie podtablic o zadanej sumie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Tworzenie tablicy sum prefiksowych
- Sumowanie dowolnego zakresu przez odejmowanie
- Zliczanie podtablic o zadanej sumie
- Tablice różnicowe do aktualizacji zakresów