作者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