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