z****e
发帖数: 2024 | 1 Given an array of integers or other numbers (reals, doubles, etc), tell us
if any two of the numbers in the array sum up to another given number.
是不是不能用hash？
不用hash怎么作呢？ |
x****r
发帖数: 99 | 2 一般这种题可以用hash的话就是O(n)呗，不然的话sort了对每一个a做binary search找
N - a，O(n*lgn)？还有别的方法么？ |
z****e
发帖数: 2024 | 3 我听说，正整数可以O(n) 排序，没找到详细资料。
我觉得如果不用hash，nlgn是不是最快了？
【在 x****r 的大作中提到】
: 一般这种题可以用hash的话就是O(n)呗，不然的话sort了对每一个a做binary search找
: N - a，O(n*lgn)？还有别的方法么？
|
c*********7
发帖数: 19373 | 4 这个题用hash也不能o(n),毕竟要算两两之和。
【在 x****r 的大作中提到】
: 一般这种题可以用hash的话就是O(n)呗，不然的话sort了对每一个a做binary search找
: N - a，O(n*lgn)？还有别的方法么？
|
z****e
发帖数: 2024 | 5 怎么不能O(n)？
先都一个个hash进去，然后都被given number减一遍，再hash，发现有冲突，OK，打印
当前number 和given number 减去当前number。
行否？
【在 c*********7 的大作中提到】
: 这个题用hash也不能o(n),毕竟要算两两之和。
|
x****r
发帖数: 99 | 6 正整数O(n)的排序，肯定也是bucket，那就是用bitArray,那样也算是一种hash了，而
且排序时间
不能说是O(n)的，如果能用bitArray，那和hashmap是一样可以O(n)时间找到的，不需
要排序，直
接看bitarray里面有没有和它相加满足条件的数字就可以了
【在 z****e 的大作中提到】
: 我听说，正整数可以O(n) 排序，没找到详细资料。
: 我觉得如果不用hash，nlgn是不是最快了？
|
