在整數陣列中查找子陣列和

給定N個正整數的數組。它可以有n*(n+1)/2子數組，包括單個元素子數組。每個子陣列有一個總和S。對於所有的子陣列，查找S's顯然是O(n^2)，因爲子陣列的數量是O(n^2)。許多和也可以重複。有沒有什麼辦法可以找到O(n logn)中所有不同總數（不是總數的確切值，而只是數）。在整數陣列中查找子陣列和

我嘗試了一種方法，但卡住了。我將數組從索引1迭代到n。
說a[i]是給定的數組。對於每個索引i,a[i]將添加到涉及a[i-1]的所有總和，並將其本身也包括爲單個元素。但如果涉及a[i-1]的款項之間出現重複，則兩筆款項的差額爲a[i]。我的意思是說，總和Sp和Sq最終在a[i-1]和兩者的差異是a[i]。然後Sp + a[i]等於Sq，給予Sq作爲重複。

說C[i]是不同的總數的計數，最終在a[i]。
所以C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i]。

但問題是要找到對的數量在O(log n)的一部分。請給我一些關於這個的暗示或者如果我在錯誤的方式和完全不同的方法是需要的問題點出來。

來源

2013-07-06 user2011120

嗯，這是一個有趣的問題。我要提出的一切都需要考慮所有輸入元素對，即O（n^2）。我的直覺說這是不可能的。 – user2357112

我一直向那些給我提出O（n logn）存在的問題的人保證。我花了整天思考。 – user2011120

如果你明天仍然堅持下去，請問他一個及時的演示，所以你知道他並沒有搞砸你。 – user2357112

當S是不是太大，我們可以算一個（快）多項式乘法的不同款項。當S較大時，N有希望足夠小以使用二次算法。

設x_1，x_2，...，x_n爲數組元素。設y_0 = 0且y_i = x_1 + x_2 + ... + x_i。令P（z）= z^{y_0} + z^{y_1} + ... + z^{y_n}。計算多項式P（z）* P（z^{ - 1}）的乘積;當k> 0時z^k的係數是非零的當且僅當k是一個子陣列和，所以我們只需要讀出非零係數的正冪數。的Z，而且，從範圍到-S S，所以乘法需要時間S的順序上的權力登錄S.

來源

2013-07-07 00:10:06

不錯，我認爲這是正確的做法。 –

這個答案已經夠長了，現在刪除它是不公平的。請不要破壞它。 –

@David很少有人正在努力解決問題，但版主忽略了他們。它是比賽的決定性問題之一。我不接受它不給任何人提示。你可以現在刪除解決方案，並在比賽結束後重新發布。之後我會將其標記爲已接受。 – user2011120

你可以看一下子陣作爲一種樹。在子數組[0,3]的意義上可以分爲[0,1]和[2,3]。

因此建立一棵樹，其中節點由子數組的長度定義，它的原始數組中盯着偏移，每當您計算一個子陣，結果存儲在這棵樹上。

當計算子陣列，可以檢查此樹現有預先計算的值。

另外，分割時，陣列的部件可以計算在不同的CPU核心，如果該事項。

此解決方案假設您不需要一次性使用所有值，而是特別設置。對於前者，可能有一些更聰明的解決方案。

此外，我假設我們正在談論10000和更多元素的計數。否則，這樣的工作是一個很好的練習，但沒有太大的實用價值。

來源

2013-07-07 00:34:03

在整數陣列中查找子陣列和

回答

相關問題