Algorytmy i struktury danych · Middle · Pytanie 57 z 75
Suma podtablicy równa k: po co trzymać liczności sum prefiksowych w mapie?
- 1Aby w ogóle nie liczyć sum prefiksowych
- 2Aby posortować sumy prefiksowe do późniejszego wyszukiwania binarnego
- ✓Poprawna odpowiedź: Podtablica kończąca się tutaj daje k, jeśli
prefix - kjuż wystąpiło
Wyjaśnienie
Suma (i, j] równa się prefix[j] - prefix[i]. Dla każdej pozycji dodaj, ile wcześniejszych prefiksów równa się prefix - k. Jedno przejście O(n), działa też z liczbami ujemnymi, w przeciwieństwie do przesuwanego okna.