由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一个给定的array 和一个sum value,找最小sub-array,谢谢
相关主题
问一道amazon的Onsite题“常数空间O(N),O(1)算法那个题目”的变形题目
给定一个数组,找出3个数乘积最大。M家SDE offer
请大牛解释一下leetcode新题给定一个值和sorted队列,只有唯一的pair其和等于给定值
再来讨论一个题!问一道题(1)
求最大subarray的和和积的问题Subset of size m Problem
G家题目讨论:所有的subarray sum 在一个 区间Random Array number, Find longest consecutive sequence
一个精华区的算法题一道老题
从水木上看到个数组题subset
相关话题的讨论汇总
话题: array话题: sum话题: 给定话题: value话题: sub
进入JobHunting版参与讨论
1 (共1页)
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
1 (共1页)
进入JobHunting版参与讨论
相关主题
subset求最大subarray的和和积的问题
问道老题G家题目讨论:所有的subarray sum 在一个 区间
贡献两道Bloomberg面试题一个精华区的算法题
请教一个算法题:矩阵找子矩阵,使得sum最大从水木上看到个数组题
问一道amazon的Onsite题“常数空间O(N),O(1)算法那个题目”的变形题目
给定一个数组,找出3个数乘积最大。M家SDE offer
请大牛解释一下leetcode新题给定一个值和sorted队列,只有唯一的pair其和等于给定值
再来讨论一个题!问一道题(1)
相关话题的讨论汇总
话题: array话题: sum话题: 给定话题: value话题: sub