Алгоритми та структури даних · Middle · Запитання 57 з 75
Сума підмасиву дорівнює k: навіщо зберігати кількості префіксних сум у хеш-таблиці?
- 1Щоб узагалі не рахувати префіксні суми
- 2Щоб відсортувати префіксні суми для подальшого бінарного пошуку
- ✓Правильна відповідь: Підмасив, що закінчується тут, дає k, якщо
prefix - kуже траплялося
Пояснення
Сума (i, j] дорівнює prefix[j] - prefix[i]. Для кожної позиції додаємо, скільки попередніх префіксів дорівнюють prefix - k. Один прохід O(n), і працює з від'ємними числами, на відміну від ковзного вікна.