Почему это работает
- Окно всегда длиной с образец и сдвигается на одну букву, поэтому проверяется каждое место, где мог бы начаться образец, и первое — первым.
- Если суммы разные, то и буквы разные: такое окно отбрасывается за O(1). Сумма обновляется, как текущая сумма: один код входит, один выходит.
- Равные суммы ещё не значат равные буквы («cbb» и «bad» обе дают 7), поэтому окно с нужной суммой всё равно сравниваем по буквам.
Сложность
Время: суммы стоят O(n + m), и ещё O(m) за каждое окно с совпавшей суммой. Если ложных тревог мало, выходит O(n + m); в худшем случае, когда нужная сумма почти у каждого окна, O(n · m). Память O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗