※ 引述《saladim (杀拉顶)》之铭言： : 有人跟我说这是一提FB的面试题目, 想了一下想不太出合适的解法, 题目如下: : 给一个sorted array, 找出array里面有没有某两个元素加起来等於另外一个元素, : 有的话请列印出来, 没有的话请回答没有. : 尝试利用 sorted元素大小关系跟binary search去做, 但是想不出来阿!!!! : 请各位大大提供一下意见.....感激不尽..... 这边提供一个另类的想法。 想像一个二维阵列 sum[i][j] = array[i] + array[j] 可以发现往右往下 sum 会变大，往左往上 sum 会变小， 其实 sum 就是一个排序过的二维阵列。 在 sum 里面做 binary search 需要 O(N) 时间。 套用前面 LPH66 与 stimim 板友推文里的解法， 穷举 array 的每一个数字，在 sum 里面二分搜寻， 总共就是 O(NN) 时间了。 那麽能不能更快呢？我也不知道... 穷举 array 的每一个数字，是由小到大穷举的话， 每一个数字在 sum 里面的二分搜寻路线，就是逐渐偏右、偏下， 这些路线应该会有很多地方重叠， 如果可以把重叠的路线省略掉的话，应该可以更快吧？ 以上 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.230.130.247