給定一個整數sum，從有N個無序元素的數組中尋找元素a、b、c、d，使得 a+b+c+d =sum，最快的平均時間複雜度是____。
正确答案: E 你的答案: C (錯誤)
O(N^2) O(log N) O(N) O(N^3) O(N^2LogN) O(N^4) - 添加筆記
- 求解答(47)
- 收藏
- 糾錯
O(N^3LogN)的算法： 三重for循環窮舉a,b,c的值，剩下d = sum-a-b-c,使用二分查找(數組事先排好序)來确定d是否存在。
O(N^2LogN)的算法： 預先枚舉c,d得到c+d的n^2個數字并排好序。 雙重for循環窮舉a,b的值，再使用二分查找确定c+d是否存在。 c+d的值得出來後同樣枚舉得出c,d的值。（或者在第一步就浪費一些空間将c+d對應的c,d存好，此時直接取出即可。)
排序及循環二分查找都為O(n^2logn)時間，總的O(n^2logn)時間。