J*****u
发帖数: 30 | 1 给定一个array,问minimum sub-array的和与sum value相等.array里可能有正数,负数
和0,sum value也有可能是正负和
0.谢谢! | J*****u
发帖数: 30 | 2 Is there any one have good answer? Thanks so much. Can it be run in O(n)
time?
【在 J*****u 的大作中提到】
: 给定一个array,问minimum sub-array的和与sum value相等.array里可能有正数,负数
: 和0,sum value也有可能是正负和
: 0.谢谢!
| e*****e
发帖数: 1275 | 3 是subarray 还是 subset.
subset 是个经典DP的题目。
subarray 就算i到n的sum好了~~然后用hash table | J*****u
发帖数: 30 | 4 是subarray,那从i到n的复杂度是不是就为n^2了? 谢谢
【在 e*****e 的大作中提到】
: 是subarray 还是 subset.
: subset 是个经典DP的题目。
: subarray 就算i到n的sum好了~~然后用hash table
| e*****e
发帖数: 1275 | 5 不是这样的。。。。
a1, a2, a3...an
先算 sum
a1, a1+a2,a1+a2+a3,....sum(an)
as
b1, b2, b3....bn
连续的和就是bi-bj = target
i-j 最小~~
然后把target + bj(j=0,...n) 放进hash
然后每个b,就在hash里面找~~~
所以应该是O(n)
不知道对不对~~请大牛指正~~~ | s******c
发帖数: 932 | 6 不太明白你的意思
bi-bj 有O(n^2)个吧
【在 e*****e 的大作中提到】
: 不是这样的。。。。
: a1, a2, a3...an
: 先算 sum
: a1, a1+a2,a1+a2+a3,....sum(an)
: as
: b1, b2, b3....bn
: 连续的和就是bi-bj = target
: i-j 最小~~
: 然后把target + bj(j=0,...n) 放进hash
: 然后每个b,就在hash里面找~~~
| a******7
发帖数: 106 | 7 kind of saw this before here, but with sum <= k | s******c
发帖数: 932 | 8 这个你有解么 当时没做出来
【在 a******7 的大作中提到】
: kind of saw this before here, but with sum <= k
| s******c
发帖数: 932 | 9 这个你有解么 当时没做出来
【在 a******7 的大作中提到】
: kind of saw this before here, but with sum <= k
|
|
