小编Eni*_*gma的帖子

我有一个大小n为整数值的数组和一个给定的 number S。

1<=n<=30

我想找到子序列的总数，使得每个子序列的元素总和小于S。 例如：让n=3，S=5和数组的元素是作为{1,2,3}然后其总的子序列是7原样

{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

但是，所需的子序列是：

{1},{2},{3},{1,2},{1,3},{2,3}

that is{1,2,3}不被采用，因为它的元素总和(1+2+3)=6大于Sthat is 6>S。之所以采用其他，是因为，对于其他子序列，元素总和小于S。因此，可能的子序列总数为6。所以我的答案是计数，即6。

我试过递归方法，但它的时间复杂度是2^n. 请帮助我们在多项式时间内完成。

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