Возможно линейное решение (извините, ранее я утверждал, что это должно быть n ^ 2), если вы осторожны, чтобы на самом деле не печатать результаты!
Во-первых, давайте определим «оценку» для любого набора нулей и единиц как количество единиц минус число нулей. Таким образом, (0,1) имеет оценку 0, в то время как (0) равно -1, а (1,1) равно 2.
Теперь начните справа. Если крайняя правая цифра равна 0, то ее можно объединить с любой группой слева, имеющей 1 балл. Таким образом, нам нужно знать, какие группы доступны слева, проиндексированные по баллу. Это предполагает рекурсивную процедуру, которая накапливает группы с оценками. Процесс развертки - это O (n), и на каждом этапе он должен проверять, создала ли он новую группу, и расширять таблицу известных групп. Проверка для новой группы является постоянным временем (поиск в хеш-таблице). Расширение таблицы известных групп также является постоянным временем (сначала я думал, что это не так, но вы можете поддерживать отдельное смещение, которое позволяет избежать обновления каждой записи в таблице).
Таким образом, у нас есть особая ситуация: каждый шаг процесса идентифицирует набор результатов размером O (n), но для этого необходимо вычислить постоянное время (в пределах этого шага). Таким образом, сам процесс по-прежнему O (n) (пропорционально количеству шагов). Конечно, на самом деле печать результатов (либо на шаге, либо в конце) делает вещи O (n ^ 2).
Я напишу немного кода Python для тестирования / демонстрации.
Вот и мы:
SCORE = [-1,1]
class Accumulator:
def __init__(self):
self.offset = 0
self.groups_to_right = {} # map from score to start index
self.even_groups = []
self.index = 0
def append(self, digit):
score = SCORE[digit]
# want existing groups at -score, to sum to zero
# but there's an offset to correct for, so we really want
# groups at -(score+offset)
corrected = -(score + self.offset)
if corrected in self.groups_to_right:
# if this were a linked list we could save a reference
# to the current value. it's not, so we need to filter
# on printing (see below)
self.even_groups.append(
(self.index, self.groups_to_right[corrected]))
# this updates all the known groups
self.offset += score
# this adds the new one, which should be at the index so that
# index + offset = score (so index = score - offset)
groups = self.groups_to_right.get(score-self.offset, [])
groups.append(self.index)
self.groups_to_right[score-self.offset] = groups
# and move on
self.index += 1
#print self.offset
#print self.groups_to_right
#print self.even_groups
#print self.index
def dump(self):
# printing the results does take longer, of course...
for (end, starts) in self.even_groups:
for start in starts:
# this discards the extra points that were added
# to the data after we added it to the results
# (avoidable with linked lists)
if start < end:
print (start, end)
@staticmethod
def run(input):
accumulator = Accumulator()
print input
for digit in input:
accumulator.append(digit)
accumulator.dump()
print
Accumulator.run([0,1,0,0,1,1,1,1,0])
И вывод:
dynamic: python dynamic.py
[0, 1, 0, 0, 1, 1, 1, 1, 0]
(0, 1)
(1, 2)
(1, 4)
(3, 4)
(0, 5)
(2, 5)
(7, 8)
Вы можете быть обеспокоены тем, что некоторая дополнительная обработка (фильтрация для start < end) выполняется в подпрограмме дампа, которая отображает результаты. Но это потому, что я работаю над отсутствием связанных списков в Python (я хочу расширить список и сохранить предыдущее значение в постоянном времени).
Может показаться удивительным, что результат имеет размер O (n ^ 2), в то время как процесс поиск результатов равен O (n), но легко увидеть, как это возможно: на одном «шаге» процесс идентифицирует количество групп (размером O (n)), связывая текущую точку (self.index в append или end в dump()) со списком конечных точек (self.groups_to_right[...] или ends).
Обновление: еще один момент. Таблица «групп справа» будет иметь «типичную ширину» записей sqrt (n) (это следует из центральной предельной теоремы - это в основном случайное блуждание в 1D). Поскольку запись добавляется на каждом шаге, средняя длина также равна sqrt (n) (значения n распределяются по ячейкам sqrt (n)). Это означает, что ожидаемое время для этого алгоритма (т.е. со случайными входами), если вы включите печать результатов, составляет O (n ^ 3/2), даже если наихудший случай равен O (n ^ 2)