從3個列表中添加3個數字的最快方法，可以添加到另一個數字中？

Question

鑑於3 分類列出L1,L2,L3所有大小n等一批x的最新最快的算法，最多可以返回到3個數字，至多從每個列表，這樣，那些返回數字的總和添加到x。

我能想到的最快的算法是檢查所有可能的組合，即O(n^3)。有沒有更好的辦法？

感謝

Answer 1

你可以得到O（n^2）：

只考慮兩個列表，L1和L2。在最大元素處設置L1中的索引，並在添加的零元素處設置L2中的索引。現在將兩個索引迭代在一起：如果所選兩個元素的總和太大，請將L1索引向下。如果所選兩個元素的總和太小，則向上提升L2索引。這需要O（2n）時間。

本質上，你正在構造一個矩形，L1的元素是一個軸，L2的元素是Y軸。然後，您走過表示總和過大的點區域和表示總和過小的點區域之間的邊界。

對L3中的每個值執行一次上述算法給出O（n^2）算法。

Answer 2

你至少可以得到O(n^2 log n)，因爲鑑於2個指數（i和j，說），你可以做L3爲x-L1[i]-L2[j]二進制搜索。

如果您不需要每個列表中的值，則可以單獨嘗試每個可能的非空列表子集;因爲那裏有6個這樣的子集，並且每個子集的求解速度都快於O(n^2 log n)（O(n log n)列表對，單個列表的O(log n)），所以總體複雜度不變。