r********t
发帖数: 395 | 1 if all the elements are positive, easy;
but what can we do if negative numbers are possible?
is there any O(n) solution? |
b********h
发帖数: 119 | 2 how do you solve it in O(n) when all the elements are positive? |
r********t
发帖数: 395 | 3 从a【0】+a【1】....一直加下去，直到你的sum大于给定的sum
然后再用你的sum一个个从a【0】开始减。。。 |
r********t
发帖数: 395 | 4 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
r********t
发帖数: 395 | 5 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
b********h
发帖数: 119 | 6 I see. Then how about find the smallest number in the array, add this number
to every element of the array and to the sum you are looking for. It is the
same problem as before. |
l*****a
发帖数: 14598 | 7 what is the result to find 7 from "6 4 2 3" with your algorithm
i think at least u need the array to be sorted
【在 r********t 的大作中提到】
: 从a【0】+a【1】....一直加下去，直到你的sum大于给定的sum
: 然后再用你的sum一个个从a【0】开始减。。。
|
J*****u
发帖数: 30 | |
h**********d
发帖数: 4313 | 9 楼住的意思应该是subsequence，这个例子里没有
【在 l*****a 的大作中提到】
: what is the result to find 7 from "6 4 2 3" with your algorithm
: i think at least u need the array to be sorted
|
f***g
发帖数: 214 | 10 这个题，几天前讨论过，老帖找不到了
要用hashtable |
J*****u
发帖数: 30 | 11 用hashtable 的那个貌似是sum为0吧,但是这里sum不为0的,可正,可负.
【在 f***g 的大作中提到】
: 这个题，几天前讨论过，老帖找不到了
: 要用hashtable
|
i**********e
发帖数: 1145 | 12 See here, this question is discussed before.
http://www.mitbbs.com/article_t/JobHunting/31791913.html
It is possible to solve this in O(N) using hash table.
The discussion above refer to sum of 0, but it can be modified easily to sum
of a specific number.
Be careful that you might miss including the first element.
See my post here for more detail:
http://www.mitbbs.com/article/JobHunting/31798127_0.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
