Определить, существует ли непрерывный подмассив длины> 1 с целым средним

Question

Учитывая несортированный массив целых чисел.

Я пытаюсь найти эффективное решение (лучше, чем O (n ² )), но лучшее, что я могу придумать, это O (n ² ) решение:

for i from 0 to size of list:
    sum = list[i]

    for j from i + 1 to size of list:
        sum += list[j]

        if sum % (j - i + 1) == 0:
            return true
return false

Я читал материал по технике скользящего окна, но, похоже, это было бы полезно для подмассивов определенной длины k .

Answer 1

Это может быть хитрый вопрос :) Два нечетных числа суммируются с четным числом, а два четных числа с четным числом.Единственный набор данных, который не будет включать в себя непрерывный подмассив длины два, который также делится на два, должен чередоваться [..., odd, even, odd, even, ...].Но тогда набор данных должен быть еще более ограничен, чтобы не допустить деления подмассива длины 4 на четыре, поскольку любое другое четное число делится на четыре.

Вероятность получения такого списка чрезвычайно великамаленький и продолжает уменьшаться по мере увеличения списка (более того, он поддается подмножеству числовых шаблонов; могут ли они быть интересными?), что означает, что если кто-то кропотливо работал над созданием некоторых, в большинстве, если не всех реальных ситуацийнашел бы решение со скользящим окном размера 4, которое также проверяет чередование четности.