許多子數組求和

子數組問題：給定整數數組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）時間進行查詢 –

回答