Поиск всех интервалов, соответствующих определенному условию

Question

Как найти все интервалы в массиве 0 с, 1 с и 2 с, которые содержат одинаковое количество 1 с и 2 с?

Пример:

[0,1,1,2,2]

Вернет 3 интервала

[0,1,1,2,2] [1,1,2,2] [1,2]

Я не хочу грубой силы. Есть ли очень простой алгоритм, который можно использовать для таких случаев? Мне нужно что-то гибкое.

Answer 1

Поставьте -1 вместо 2 в исходном массиве. Тогда проблема будет сведена к следующему: Нулевая сумма SubArray

Answer 2

Во-первых, для ясности в алгоритме я собираюсь заменить цифры на буквы: Z, A, B. Теперь ввод можно представить в виде простой строки: «ZAABB». Также для ясности я собираюсь вставить точку в каждой позиции, для интервала: ".Z.A.A.B.B.".

Это проблема балансировки символов, достаточно простая для решения. Итерация по массиву, отслеживание избытка в каждой позиции. Z не меняет счет; A приращения; B декременты. Это дает нам

"00011221100".  

Теперь, извлеките альтернативные значения, количество в каждой "прокладке", периоды:

".Z.A.A.B.B."
"0 0 1 2 1 0"

Отсюда просто найти подходящее количество. Каждая пара совпадений дает вам индексы подстроки с одинаковым количеством A и B. У вас есть три пары из 0 совпадений и одна пара из 1 совпадений, что дает подстроки

" 0 0 1 2 1 0" Z

" 0 0 1 2 1 0 " Z A A B B

"0 0 1 2 1 0 " A A B B

"0 0 1 2 1 0" A B

Это достаточно ясно для реализации?