Найти все возможные комбинации подмассивов в большем массиве int на основе заданного шаблона

Question

Учитывая массив int, состоящий только из 1 и 0, например [1,0,0,1,0,0,0,1], я хочу получить все возможные вложенные массивы, которые будут начинаться и заканчиваться на 1.

Как и в этом случае, на выходе будут три массива:

• [1,0,0,1]
• [1,0,0,0,1]
• [1,0,0,1,0,0,0,1]

Это все три возможные комбинации.

Я сделал это сO (n ^ 2) временная сложность, но я хочу более эффективное решение.

Какой алгоритм подойдет для этого случая?Я использую Java для реализации.

Answer 1

Если вы просто хотите найти количество массивов, которые начинаются и заканчиваются на 1, то это можно решить с помощью простой формулы.

Проблема сводится к решению, т. Е. К Number of ways to select any 2 indices of 1's in the given array.

Теперь это может быть задано формулой: N (N-1) / 2, где N - число единиц в данном массиве.

Таким образом, вам придется пройти как минимум по всему массивуодин раз.Поэтому сложность времени уменьшается до O(Size of Array) ~ O(n).