[問題] 貌似Facebook面試題目

[saladim (殺拉頂)]

有人跟我說這是一提FB的面試題目, 想了一下想不太出合適的解法, 題目如下:

給一個sorted array, 找出array裡面有沒有某兩個元素加起來等於另外一個元素,

有的話請列印出來, 沒有的話請回答沒有.


嘗試利用 sorted元素大小關係跟binary search去做, 但是想不出來阿!!!!


請各位大大提供一下意見.....感激不盡.....

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.43.203.126
推 ledia:3 sum problem 的小變形, google 一下就有, O(n^2) 解法
→ saladim:?? 要等於的那個元素不是給定的 是陣列內要找出來的
→ saladim:等等我去辜狗一下
→ yauhh:你說想不出來是任何一個基本解都想不出來嗎?
→ LPH66:再怎麼想不到解好歹最簡單的 O(n^3) 的做法應該要想得到...
推 LPH66:O(n^2) 的提示: 兩層迴圈的其中一層是固定陣列某個元素
→ LPH66:當做加的其中之一
→ bleed1979:固定沒錯，但應該是當作如何移動索引的判斷？
→ stimim:給定和的話，可以在 O(n) 找到兩個元素
→ chunhsiang:包含負數嗎?
推 st900278:N^2logN 再加上cut 會過嗎?
推 Favonia:http://maven.smith.edu/~orourke/TOPP/P11.html
→ ilway25:原來已經有人證出lower bound了..
推 Austin9:同Stimim大，可以在O(n)完成。