作者saladim (殺拉頂)
看板Prob_Solve
標題[問題] 貌似Facebook面試題目
時間Sat Mar 17 12:11:15 2012
有人跟我說這是一提FB的面試題目, 想了一下想不太出合適的解法, 題目如下:
給一個sorted array, 找出array裡面有沒有某兩個元素加起來等於另外一個元素,
有的話請列印出來, 沒有的話請回答沒有.
嘗試利用 sorted元素大小關係跟binary search去做, 但是想不出來阿!!!!
請各位大大提供一下意見.....感激不盡.....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.203.126
1F：推 ledia:3 sum problem 的小變形, google 一下就有, O(n^2) 解法 03/17 12:31
2F：→ saladim:?? 要等於的那個元素不是給定的 是陣列內要找出來的 03/17 12:58
3F：→ saladim:等等我去辜狗一下 03/17 12:58
4F：→ yauhh:你說想不出來是任何一個基本解都想不出來嗎? 03/17 13:28
5F：→ LPH66:再怎麼想不到解好歹最簡單的 O(n^3) 的做法應該要想得到... 03/17 14:43
6F：推 LPH66:O(n^2) 的提示: 兩層迴圈的其中一層是固定陣列某個元素 03/17 14:47
7F：→ LPH66:當做加的其中之一 03/17 14:47
8F：→ bleed1979:固定沒錯，但應該是當作如何移動索引的判斷？ 03/17 16:25
9F：→ stimim:給定和的話，可以在 O(n) 找到兩個元素 03/17 16:53
10F：→ chunhsiang:包含負數嗎? 03/17 21:24
11F：推 st900278:N^2logN 再加上cut 會過嗎? 03/22 00:09
13F：→ ilway25:原來已經有人證出lower bound了.. 03/23 12:44
14F：推 Austin9:同Stimim大，可以在O(n)完成。 03/26 00:05