Почему это работает
- Сумма подмассива — это сумма с начала до его конца минус сумма до его начала. Значит, подмассив, который кончается здесь, даёт k ровно тогда, когда раньше был префикс prefix − k, а seen говорит, сколько таких префиксов было.
- seen начинается с {0: 1} — пустого префикса до индекса 0. Без него [1, 2] и [1, 2, -1, 3, -2], которые начинаются с индекса 0, не посчитались бы.
- Из-за отрицательных чисел не работает скользящее окно: сумма падает и снова растёт, как в [1, 2, -1, 3, -2]. Разности префиксов знаки не мешают.
Сложность
Время O(n): один проход, а поиск и запись в словаре в среднем O(1). Память O(n): в seen может оказаться n + 1 разных префиксов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗