考虑一个数组(基于 0 的索引)我必须找到不同的总和 所有可能范围 [i,n] 的元素,其中 0< i < n
示例:
arr={1,2,1,3}
sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3
O(n^2) 解决方案是一种可能的解决方案,虽然我找不到好的教程,但我已经阅读了持久线段树也可以做到这一点。
能否在小于 O(N^2) 的时间内解决?
如果有人指出持久线段树请解释或提供一些好的链接?
最佳答案
这可以通过简单的动态规划算法在 O(n) 中完成。
从数组的后面开始,使用一个基于散列的容器来存储你已经遇到过的数字。最后一个元素的值,即 sum_range[n-1]
设置为 arr[n-1]
。之后,sum_range[i]
的值应计算如下:
- 如果
arr[i]
不在所见数字的集合中,sum_range[i] = sum_range[i+1]+arr[i]
- 否则,
sum_range[i] = sum_range[i+1]
由于检查散列容器中的值的成本是 O(1) 并且将项目添加到散列容器的成本对于 n 个项目分摊 O(1),因此该算法的总成本是 O(n) .
与使用O(1)空间的O(n2)算法相比,该算法为哈希容器使用了额外的O(n)空间。
关于algorithm - 范围内不同元素的总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34557962/