Равное количество 0 и 1

Постановка задачи

nums = [0, 1]

2

nums = [0, 1, 0]

2

Решение

Задача выглядит как обычный перебор подмассивов: взять каждую левую границу, затем каждую правую границу и посчитать количество нулей и единиц. Такой подход работает, но он слишком медленный. Подмассивов в массиве O(n²), а ограничение 10⁵ сразу говорит нам, что нужен линейный алгоритм.

Подумайте немного, каким образом мы могли бы использовать префиксные суммы для решения. Нам нужно быстро определять, что подмассив содержит одинаковое количество нулей и единиц. Мы уже знаем, что префиксный массив позволяет за O(1) получать сумму на любом подмассиве. Значит, префиксные суммы хорошо подходят и для этой задачи.