子数组问题:给定整数数组A(只有正数),是否存在任意长度的连续子数组,其和为S?对此的滑动窗口解决方案是 O(N)。
现在如果我们在静态数组上有很多这样的查询 S,我们可以进行预处理。我们可以计算 O(N^2) 中的所有子数组和并将它们存储在哈希表中。这也占用 O(N^2) 空间。然后我们可以在 O(1) 中处理查询,只需从哈希表中查找 S
我的问题是,是否有一些 O(N log N) 的预处理?即使这意味着将查询降低到 O(log N)。
最佳答案
is there some O(N log N) prepeprocessing?
不。
在大小为 N 的数组中有 N2 个可能的子数组。您不能在小于 O(N2) 时间。
关于arrays - 许多子数组求和查询,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46386866/