搜索多個排序數組及其複雜度

Question

給定3個排序數組。查找3個元素，每個數組中有一個元素，使a + b = c。它可以做到小於O（n^3）的時間複雜度嗎？請幫幫我。

Answer 1

它可以在O（N^2 * logN）複雜性中通過遍歷2個數組a和b和二進制搜索c在第三個數組中完成。

另一種方法是通過將其中一個數組的元素插入到散列中，對另外兩個數組中的a和b進行迭代，並查看c中是否存在c =（a + b）哈希值。

Answer 2

呼叫三個陣列A，B和C，並且這些元件a，b和c。

while循環前兩個數組，因爲如果a是固定的，b只能增加，c也只能增加。

所以你不必通過C循環每次你有一對a和b;只是循環通過C雖然循環雖然B會做。

假設現在所有三個陣列具有長度O（N）的時間複雜度爲O（N^2），由於在A每一個值，你需要經過所有的B和所有的C，其數量是O（N）。