Найти сумму всех последовательных подмассивов длины k в данном массиве
Я хочу узнать всю сумму непрерывного подмассива длины K
для данного массива длины n При условии k < n, Например, пусть данный массив будет arr[6]={1,2,3,4,5,6} а также k=3тогда ответ (6,9,12,15),
Его можно получить как:
(1+2+3)=6,
(2+3+4)=9,
(3+4+5)=12,
(4+5+6)=15.
Я пробовал это с помощью скользящего окна длины k, но сложность его времени O(n). Любое решение, которое занимает еще меньше времени, такое как O(log n),
Решение
Если вы не знаете определенные специфические свойства массива (например, порядок элементов, диапазон элементов, включенных в массив и т. Д.), Вам придется проверять каждое отдельное значение, что приводит к O(n) сложность.
Если, например, вы знали, что сумма значений в массиве T (возможно, потому что вы знали T сам или дали диапазон), то вы могли бы считать, что все элементы, кроме первого и последнего (K-1) элементы будут включены в K разные суммы. Это будет означать сумму T.K минус некоторое количество, и вы можете уменьшить значения первого и последнего K значения соответствующее количество раз, в результате чего алгоритм сложности O(K),
Но учтите, что для достижения стратегии, подобной этой, вам необходимо знать некоторую другую конкретную информацию о значениях в массиве, будь то их диапазон или их сумма.
Другие решения
Вы можете использовать структуру данных дерева сегментов, хотя для ее построения потребуется O (n log n), но вы можете найти сумму любого интервала в O (log n) и изменить каждый элемент массива в O (log n).
https://en.wikipedia.org/wiki/Segment_tree