Постановка задачи :
Вам дан массив/список ARR длины N, состоящий только из 0 и 1. Ваша задача — найти количество подмассивов (непустых), в которых количество нулей и единиц равно.
Пример ввода:
7 1 0 0 1 0 1 1
Пример вывода:
8
Объяснение примера тестового примера:
Имеется 8 таких подмассивов с диапазоном индексов [0, 1], [2, 3], [0, 3], [3, 4], [4, 5], [2, 5], [0, 5], [1, 6].
Подход :
МЕТОД КУМУЛЯТИВНОЙ СУММЫ
Если мы рассмотрим каждый «0» как -1, то подмассив, содержащий равные 0 и 1, даст сумму 0. Таким образом, мы можем использовать кумулятивную сумму для подсчета эти подмассивы с суммой 0 легко.
Идея основана на том факте, что если совокупная сумма снова появится в массиве, то подмассив между этими двумя вхождениями накопленной суммы будет иметь сумму из 0.
Например-
Учитывая ARR = [1, 1, 1, 0, 0, 1]
Совокупная сумма = [1, 2, 3, 2, 1, 2]
Здесь один из требуемых подмассивов имеет индекс range[1, 4]. Мы видим, что 1 снова появляется в кумулятивной сумме с индексом 4 (ранее с индексом 0). Следовательно, подмассив между индексом 0 (исключительно) и индексом 4 (включительно) является одним из подмассивов с равными 0 и 1.
Алгоритм:
Временная сложность: O(N)
Пространственная сложность: O(N)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
