Быстрый способ проверить последовательные подпоследовательности для всего

Question

У меня есть список (длиной до 10000) чисел 0, 1 или 2. Мне нужно посмотреть, сколько последовательных подпоследовательностей имеет общее число, которое НЕ равно 1. Мой текущий метод заключается в том, чтобы для каждого списка сделать:

cons = 0
for i in range(seqlen+1):
    for j in range(i+1, seqlen+1):
        if sum(twos[i:j]) != 1:
            cons += 1

Таким образом, пример ввода будет:

[0, 1, 2, 0]

, а вывод будет

cons = 8

, поскольку 8 рабочих подпоследовательностей:

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

Проблема в том, что простое выполнение всех этих подпоследовательностей (i в диапазоне, j в диапазоне) занимает почти больше времени, чем разрешено, а когда добавляется оператор if, выполнение кода на сервере занимает слишком много времени , (Для ясности, это лишь малая часть более крупной проблемы, я не просто прошу решение всей проблемы). В любом случае, есть ли другой способ проверить быстрее? Я не могу придумать ничего такого, что не приводило бы к тому, что каждый раз приходилось выполнять больше операций.

Answer 1

Мне кажется, я вижу проблему: ваша терминология неверна / избыточна. По определению подпоследовательность представляет собой последовательность последовательных элементов.

Не суммируйте каждого кандидата. Вместо этого определите каждого кандидата, чья сумма равна 1, а затем вычтите эту сумму из вычисленного количества всех подпоследовательностей (простая алгебра).

Все кандидаты с 1 суммой имеют форму регулярного выражения 0*10*: a 1, окруженный любым количеством 0 s с одной или обеих сторон.

Идентифицируйте все такие строки максимальной длины. Например, в

210002020001002011

вы выберете 1000, 000100, 01 и 1. Для каждой строки вычислите количество подстрок, содержащих 1 (простое уравнение для длин 0 s с каждой стороны). Сложите эти количества. Вычтите из общей суммы для всего ввода. Вот тебе ответ.

Answer 2

Используйте технику скользящего окна для решения подобных проблем. Возьмите две переменные, чтобы отслеживать первую и последнюю, чтобы отслеживать область окна. Итак, вы начинаете с суммы, равной первому элементу. Если сумма больше требуемого значения, вы вычитаете первый элемент из суммы и увеличиваете сумму на 1. Если сумма меньше требуемой, вы добавляете следующий элемент указателя «последний» и увеличиваете последний на 1. Каждый раз, когда сумма равна с необходимым приращением некоторого счетчика.

Что касается НЕ, подсчитать количество подпоследовательностей, имеющих сумму '1', а затем вычесть из общего числа возможных подпоследовательностей, т.е. n * (n + 1) / 2