在给定数组中找到长度为k的所有连续子阵列的总和

Question

我想找出长度的连续子阵列的所有总和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).

Answer 1

除非您知道数组的某些特定属性(例如元素的排序,数组中包含的元素的范围等),否则您需要检查每个单独的值,从而导致O(n)复杂性.

例如,如果您知道数组中值的总和T(可能是因为您了解T自己或给出了范围),那么您可以认为除了第一个和最后一个(K-1)元素之外的所有元素都将包含在K不同的总和中.这将意味着T.K减去一定数量的总和,并且您可以K适当地减少第一个和最后一个值的值,从而产生复杂度的算法O(K).

但请注意,为了实现类似于此的策略,您必须知道有关数组中值的其他一些特定信息,可能是它们的范围或它们的总和.