许多子数组求和

子数组问题：给定整数数组A（只有正数），是否存在任意长度的连续子数组？滑动窗口解决方案是O（N）。许多子数组求和

现在，如果我们在静态数组上有很多这样的查询S，我们可以进行预处理。我们可以计算O（N^2）中的所有子数组总和并将它们存储在散列表中。这也占用O（N^2）空间。然后我们可以在O（1）中处理查询，只是从哈希表中查找S

我的问题是，是否有一些O（N log N）预处理？即使这意味着将查询放到O（log N）。

什么是滑动窗口解决方案是O（N）方法？你有没有完全明确的问题？ – MBo

您是否完全了解众所周知的基本子数组总和问题？ –

这似乎有点难以选择一个子数组，你将不得不选择两个指数蚂蚁相当于O（N ** 2） –

是否有一些O（N log N）预处理？

否。

有N个大小N.不能在小于Ö产生大小为N 输出（N ）时间的阵列的子阵列可能。

2017-09-24 09:08:02 gsamaras

我不需要使用N log N预处理来生成N^2哈希表。目标是在* some *之后完成预处理，可以用最差的O（log N）时间进行查询 –

回答