6SUM：給定n個整數的集合S，是否有S的子集，正好有6個元素，總和爲0？如何比O（n^3）做得更好？

我想到了這個簡單的算法來解決使用O（n^3）時間和空間的6SUM問題：生成所有三元組並將它們放入散列表中，其中鍵是三元組的總和。然後遍歷哈希表的密鑰：對於每個密鑰k1，查看是否存在另一個密鑰k2，使得k2 = S-k16SUM：給定n個整數的集合S，是否有S的子集，正好有6個元素，總和爲0？如何比O（n^3）做得更好？

什麼是更高效的算法？這不是一個家庭作業問題。

聽起來非常像揹包問題給我。 http://en.wikipedia.org/wiki/Knapsack_problem – tdammers 2011-03-18 13:16:59

數字的範圍是什麼。如果要使用揹包，複雜性將取決於值的範圍。 – 2011-03-18 13:20:22

我認爲問題比揹包更容易。例如，3SUM問題可以在O（n^2）中解決。假設數字可以是任何整數 – 2011-03-18 13:25:04

在最糟的情況下，你的算法是Omega（n^6），在平均情況下它只有O（n^3）。你忽略了散列表碰撞的可能性。不過，您可以使用平衡樹來代替O（n^3 logn）。

此外，這是在P，因爲有一個平凡的多項式時間算法來檢查每個可能的6個數字的組合，所以提及揹包等是無關緊要的。我認爲r-sum問題的算法是o（n^[r/2]），（注意：smallOH和[x] =最大整數> = x，例如[5/2] = 3）仍然開放。

在3-SUM頁面here中有一個簡短的提及，其中有一個聲明上面的界限已經在受限制的計算模型中得到證實。因此，比O（n^3）（即o（n^3））好得多可能是一個公開的問題。

2011-03-18 15:29:56

回答