y***e
发帖数: 32 | 1 条件：array可以有重复的值，每个元素只能用一次。
能想到最好的解法是使用两个指针，从两边向中间挤压。时间是O(n)，空间O(1)
有时间是O(log n)的解法吗？ |
r*******k
发帖数: 1423 | 2 不可能有o(logn)的解法啊
如果下面这样的
1 2 3 4 5 6 7
找和为8的
难道不需要遍历所有的元素么？
【在 y***e 的大作中提到】
: 条件：array可以有重复的值，每个元素只能用一次。
: 能想到最好的解法是使用两个指针，从两边向中间挤压。时间是O(n)，空间O(1)
: 有时间是O(log n)的解法吗？
|
b*****r
发帖数: 25 | |
y***e
发帖数: 32 | 4 能详细解释一下如何用 binary search 达到 O(log n)吗？
从二楼给的例子来看，任何solution至少都是O(n)的，因为每个元素至少扫描一次，即
便是binary search based的solution。
【在 b*****r 的大作中提到】
: 用binary search的方法
|
y*******8
发帖数: 112 | 5 不可能的，最坏情况下有 N/2 pairs的结果都是等于target。你光是访问N/2 pairs这
些元素就是O(N)了。
【在 y***e 的大作中提到】
: 能详细解释一下如何用 binary search 达到 O(log n)吗？
: 从二楼给的例子来看，任何solution至少都是O(n)的，因为每个元素至少扫描一次，即
: 便是binary search based的solution。
|
Z**********4
发帖数: 528 | 6 如果面试官需要你给出logn的解法的话它就是在黑你。 |
