logo
Redian新闻
>未名空间
>Biology - 生物学
>
感觉留在国内晋升蛮快的
avatar
感觉留在国内晋升蛮快的# Biology - 生物学
v*d
1 楼
公司名就不说了，估计版上没几个人听说过。个人觉得挺难的，主要是以前没碰到过
给一个array, 判断是否有subarray的sum是0. 要求O(n)算法
给一个array, 给一个given number k, 给出最长的subarray的length, 这个subarray
的sum大于或等于k.要求O(nlogn)算法
被那个经典的maximal sum subarray的题误导了，一开始就没想到正点上去。都是面试
官给了hint才做出来，悲剧。。move on了
avatar
n*q
2 楼
准备买这个steam shower unit,大家觉得划算么？ 尽管拍砖。
我们是准备把half bath 改成 full bath, contractor 开价5000美刀以上。后来看到
这个steam shower unit， 价钱999美刀，免运费无税，大小都合适，但showroom 在ohio,没法亲身看。要自己
安装，但是有说明。搜了一下，好像是 make in china 的。 就是没有其他人的使用评
价。 大家觉得划算么？
×××××××××××××××××××××××××××××
LUXURY SPAS STEAM SHOWER & BATHTUB
FEATURES
Standard 110V
Computer control Heavy-Duty Acrylic &
Tempered Glass
Steam sauna Exhaust Fan
Hydr
avatar
r*y
3 楼
海盗船的 tx650 电源
haf 912的机箱
DELL 2412M 显示器
das 蓝轴键盘
人在MA北部 有人当面交易么?? 这些邮寄起来应该挺重的
其他小零件都拆了带走算了...
avatar
i*e
4 楼
不太熟悉国内的晋升要求，但国内的很多30岁出头，很多都是副教授了，那么好好的发
展40岁左右应该升正教授了吧。
我等回去如果从讲师做起，赶不上啊...
avatar
t*d
5 楼
solution for 1.)
go over array, sum up for all elements upto the current one. put the result
in a hashmap, if any value appear more than once, there's a subarray sums to
0
avatar
e*t
6 楼
能给个连接么？

ohio,没法亲身看。要自己

【在 n**q 的大作中提到】
: 准备买这个steam shower unit,大家觉得划算么？ 尽管拍砖。
: 我们是准备把half bath 改成 full bath, contractor 开价5000美刀以上。后来看到
: 这个steam shower unit， 价钱999美刀，免运费无税，大小都合适，但showroom 在ohio,没法亲身看。要自己
: 安装，但是有说明。搜了一下，好像是 make in china 的。 就是没有其他人的使用评
: 价。 大家觉得划算么？
: ×××××××××××××××××××××××××××××
: LUXURY SPAS STEAM SHOWER & BATHTUB
: FEATURES
: Standard 110V
: Computer control Heavy-Duty Acrylic &
avatar
W*n
7 楼
难说。
avatar
g*s
8 楼
is it some high-profile startup? so what are the hints?
the 2nd one smells still like a dp.

subarray

【在 v*****d 的大作中提到】
: 公司名就不说了，估计版上没几个人听说过。个人觉得挺难的，主要是以前没碰到过
: 给一个array, 判断是否有subarray的sum是0. 要求O(n)算法
: 给一个array, 给一个given number k, 给出最长的subarray的length, 这个subarray
: 的sum大于或等于k.要求O(nlogn)算法
: 被那个经典的maximal sum subarray的题误导了，一开始就没想到正点上去。都是面试
: 官给了hint才做出来，悲剧。。move on了
avatar
i*e
9 楼
我曾经在homedepot问过卖shower的人，有人说这样的shower系统一旦某个零件出问题
，整个都不能用了。
avatar
k*0
10 楼
我以前带的师弟已经教授了，但带我的老师还是讲师。
avatar
i*9
11 楼
nice!

result
sums to

【在 t**d 的大作中提到】
: solution for 1.)
: go over array, sum up for all elements upto the current one. put the result
: in a hashmap, if any value appear more than once, there's a subarray sums to
: 0
avatar
n*q
12 楼
链接是这个
http://www.luxuryspasinc.com/store/product2.html
那个sales说5年保修，零件坏了给换新的。但要自己换。
查了一下，是中国浙江那边造的，离岸价格200-400美金，可以自己直接从中国进口么
？
avatar
a*e
13 楼
不是还有国内的教授不做了，过来做薄厚陪老婆孩子的吗。想想就平衡了。
avatar
v*d
14 楼
恩，是的。第一题前面有人贴出答案了，第二题用binary search做

【在 g*********s 的大作中提到】
: is it some high-profile startup? so what are the hints?
: the 2nd one smells still like a dp.
:
: subarray
avatar
c*r
15 楼
能发SCI就快
发不出来的话，呵呵呵呵。。。
avatar
v*d
16 楼
恩，是的。第一题前面有人贴出答案了，第二题提示和第一题差不多，但不用
hashtable, 用binary search

【在 g*********s 的大作中提到】
: is it some high-profile startup? so what are the hints?
: the 2nd one smells still like a dp.
:
: subarray
avatar
s*u
17 楼
我以前母校复旦大学从讲师声副教授15：1
一个学院一年100人升报只有6-7人上副教授
哪里快了，有的人讲师15年了，还是讲师。
好的学校非常困难的

【在 i****e 的大作中提到】
: 不太熟悉国内的晋升要求，但国内的很多30岁出头，很多都是副教授了，那么好好的发
: 展40岁左右应该升正教授了吧。
: 我等回去如果从讲师做起，赶不上啊...
avatar
g*s
18 楼
good one.

result
sums to

【在 t**d 的大作中提到】
: solution for 1.)
: go over array, sum up for all elements upto the current one. put the result
: in a hashmap, if any value appear more than once, there's a subarray sums to
: 0
avatar
t*d
19 楼
how do you solve second problem using binary search? unless you only have
positive numbers. i.e. the result array of sums is sorted.

【在 v*****d 的大作中提到】
: 恩，是的。第一题前面有人贴出答案了，第二题提示和第一题差不多，但不用
: hashtable, 用binary search
avatar
t*d
20 楼
that's the thing, if you have negative numbers, you can't "Adjust your guess
of subarray length based on whehter there is a subarray sum > K. "

[0]=0)
length
look up, sum[i+m]-sum[i]]). Adjust your guess of subarray length based on
whehter there is a subarray sum > K.
avatar
b*n
21 楼
so you are assuming there is some relation between the subarray len and
the sum? The longer the length the bigger or smaller the sum?
this may not be the case

[0]=0)
length
look up, sum[i+m]-sum[i]]). Adjust your guess of subarray length based on
whehter there is a subarray sum > K.
have
avatar
j*u
22 楼
and if there's no negative number, the result will always be the whole array
if exists, correct?

guess

【在 t**d 的大作中提到】
: that's the thing, if you have negative numbers, you can't "Adjust your guess
: of subarray length based on whehter there is a subarray sum > K. "
:
: [0]=0)
: length
: look up, sum[i+m]-sum[i]]). Adjust your guess of subarray length based on
: whehter there is a subarray sum > K.
avatar
v*d
23 楼
Yes. So we do have negative numbers. Sorry the hint I gave previously is a
little bit misleading.
Suppose the original array is [-2, 2, -1, 3, -6] and k=3 then the subarrays
would be [2, -1, 3] and [3], and therefore the answer (maximal length) is 3
the idea is, first we build a sum array like before: sum=[-2, 0, -1, 2, -4],
then sort it together with the indexes, and we get (first is the number,
second is the index) x=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)], then
use two pointers i and j, i points to the beginning of x, and j points to
the end of x. if j.num-i.num>=k, length=max(length, j.index-i.index), i++, j
avatar
b*n
24 楼
i++ j-- does not seem correct, cause you disgard the case
that the same j with a larger i, j.num - i.num >= k, and the
length can be larger, you need to check every j agaist i, or vise versa
that's O(n^2)

a
subarrays
3
],
j

【在 v*****d 的大作中提到】
: Yes. So we do have negative numbers. Sorry the hint I gave previously is a
: little bit misleading.
: Suppose the original array is [-2, 2, -1, 3, -6] and k=3 then the subarrays
: would be [2, -1, 3] and [3], and therefore the answer (maximal length) is 3
: the idea is, first we build a sum array like before: sum=[-2, 0, -1, 2, -4],
: then sort it together with the indexes, and we get (first is the number,
: second is the index) x=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)], then
: use two pointers i and j, i points to the beginning of x, and j points to
: the end of x. if j.num-i.num>=k, length=max(length, j.index-i.index), i++, j
avatar
g*s
25 楼
u r sorting with the sum value, not the index...

is a
subarrays
length) is 3
2, -4],
number,
then
to
i++, j

【在 v*****d 的大作中提到】
: Yes. So we do have negative numbers. Sorry the hint I gave previously is a
: little bit misleading.
: Suppose the original array is [-2, 2, -1, 3, -6] and k=3 then the subarrays
: would be [2, -1, 3] and [3], and therefore the answer (maximal length) is 3
: the idea is, first we build a sum array like before: sum=[-2, 0, -1, 2, -4],
: then sort it together with the indexes, and we get (first is the number,
: second is the index) x=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)], then
: use two pointers i and j, i points to the beginning of x, and j points to
: the end of x. if j.num-i.num>=k, length=max(length, j.index-i.index), i++, j
avatar
v*d
26 楼
恩，还是有问题。有高人出来讲解一下不？

【在 b******n 的大作中提到】
: i++ j-- does not seem correct, cause you disgard the case
: that the same j with a larger i, j.num - i.num >= k, and the
: length can be larger, you need to check every j agaist i, or vise versa
: that's O(n^2)
:
: a
: subarrays
: 3
: ],
: j
avatar
l*l
27 楼
Here is a thought:
With the sorted index-value array x as above:
1. Left pointer start from x[0], using binary search (or linear search,
won't affect
overall big-O complexity ) find the first j (right pointer) such that
x[j].num-x[0].num>k;
then from j to the end, find the largest index, let it be m.
2. Now move left pointer to x[1], move right pointer from j to the left,
until we find the first j'
such that x[j'].num-x[1].num>k. Compare new indexes with m, update the new
m
. Also update the largest length found.
3. Continue until left index > right index.
The complexity for above steps is O(n) because each value is
compared only once. So the overall complexity is O(NlgN) bound by sort.
avatar
i*d
28 楼
借助sum数组
sum[i] = SUM{ a[i] | i = 0~i}
1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
i的值。这样遇到相同的就说明sum[i] == sum[j], jconflit。O(n)
2. 1)还是计算sum[i]。O(n)
2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
index数组了。 O(n)
4) i = 0~n-1, 对于每个i, 在排序好的sum[i]数组中找 sum[j] 正好 <= sum[i]-
k。那么以a[i]为终点的满足条件的subarray最长的长度就是 i-min_index[i]。通过一
个临时变量max记录并更新这个长度，遍历完就可以知道最大长度了。
总体可以到O(nlgn)，缺点就是得多弄几个辅助数组。。。

subarray

【在 v*****d 的大作中提到】
: 公司名就不说了，估计版上没几个人听说过。个人觉得挺难的，主要是以前没碰到过
: 给一个array, 判断是否有subarray的sum是0. 要求O(n)算法
: 给一个array, 给一个given number k, 给出最长的subarray的length, 这个subarray
: 的sum大于或等于k.要求O(nlogn)算法
: 被那个经典的maximal sum subarray的题误导了，一开始就没想到正点上去。都是面试
: 官给了hint才做出来，悲剧。。move on了
avatar
Z*Z
29 楼
这个不错，顶一下

和
min_

【在 i****d 的大作中提到】
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
: index数组了。 O(n)
avatar
m*m
30 楼

借助sum数组
sum[i] = SUM{ a[i] | i = 0~i}
1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
i的值。这样遇到相同的就说明sum[i] == sum[j], jconflit。O(n)
2. 1)还是计算sum[i]。O(n)
2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
index数组了。 O(n)
4) i = 0~n-1, 对于每个i, 在排序好的sum[i]数组中找 sum[j] 正好 <= sum[i]-
k。那么以a[i]为终点的满足条件的subarray最长的长度就是 i-min_index[i]。通过一
~~~~~~~~~~~~~
这个应该是min_index[j]，是么？
个临时变量max记录并更新这个长度，遍历完就可以知道最大长度了。
总体可以到O(nlgn)，缺点就是得多弄几个辅助数组。。。

【在 i****d 的大作中提到】
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
: index数组了。 O(n)
avatar
i*d
31 楼
啊对。。。。多谢指出来。。。已经改正了~

和
min_

【在 m******m 的大作中提到】
:
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
avatar
w*k
32 楼

和
min_
能再详细解释下这句话吗
min_index[i]是比sum[i]小的元素中的最小的下标。
以上面帖子中的例子为例，排序后的sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,
3)]
排序后的sum[0]=-4, 比sum[0]小的没有，默认min_index[0]=4 还是min_index[0] = 0?

【在 i****d 的大作中提到】
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
: index数组了。 O(n)
avatar
c*t
33 楼
我理解 应该是 4 【(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)】的最小下标是【4
,0,0,0,0】

,
0?

【在 w*****k 的大作中提到】
:
: 和
: min_
: 能再详细解释下这句话吗
: min_index[i]是比sum[i]小的元素中的最小的下标。
: 以上面帖子中的例子为例，排序后的sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,
: 3)]
: 排序后的sum[0]=-4, 比sum[0]小的没有，默认min_index[0]=4 还是min_index[0] = 0?
avatar
c*t
34 楼
赞， 我想不出有啥其他办法。

和
min_

【在 i****d 的大作中提到】
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
: index数组了。 O(n)
avatar
S*z
35 楼
谁来解析一下为什么得先求这个最小下标，思路是啥？
然后后面的为每个i找j怎么就是O(nlgn)了？

【4
(2
=

【在 c********t 的大作中提到】
: 我理解 应该是 4 【(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)】的最小下标是【4
: ,0,0,0,0】
:
: ,
: 0?
avatar
i*e
36 楼
Very interesting question!
I recognized this problem as an exercise from the classic "Programming
pearls" 2nd edition by Jon Bentley, Prob. 10, pp. 85.
1) Just like ibread mentioned, use a cumulative array where cum[i] = A[0] +
A[1] + ... A[i], which can be built using a one-pass scan. If there exist at
least one contiguous subarray which sum is equals 0, there must exist
duplicates in the cumulative array. We can use a hash table to detect
duplicates in the cumulative array in O(N),
2) Prob. 2 is just an extension to prob. 1. The required O(N lg N) already
gave some hints that you have to use sorting. First, sort the cumulative
array (each array element should also keep track of its original indices (
can be stored in a structure)). Then, do binary search on each sorted
cumulative array (i) to find the lowest element's index (j) such that cum[i]
+ k >= cum[j]. To get the largest range, we also need to keep track of the
min_index and max_index, which can be built using two tables with a one-pass
scan from right to left. The largest range for this fixed index i
would be max(max_index[j], cum[i].orig_index) - min(min_index[j], cum[i].orig_
index). Update the current maximum range if required. Then repeat the
next i. The sorting takes N lg N time. The searching for the largest range
also takes N traversal, each of them doing a lg N binary search. Therefore,
the overall complexity is O(N lg N).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
avatar
i*e
37 楼
This is incorrect.
Assume that the pair (x, y) = (cumulative sum up to ith element, its original
index before sort),
pair = {(-4, 4), (-2, 0), (-1, 2), (0, 1), (2, 3)}
then the min_index array is { 0, 0, 1, 1, 3 }
the max_index array is { 4, 3, 3, 3, 3 }
Both arrays could be built in O(N) by traversing from right to left.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【4

【在 c********t 的大作中提到】
: 我理解 应该是 4 【(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)】的最小下标是【4
: ,0,0,0,0】
:
: ,
: 0?
avatar
i*e
38 楼
Your ideas are mostly right, however you missed one important observation. To
determine the largest range, the max_index array (not just the min_index
array) is needed too.
I give an example:
A[] = {5, -3, 2, -2, 1, 4, -3, -5, 6, 4, -2}
cum[] = {5, 2, 4, 2, 3, 7, 4, -1, 5, 9, 7}
sorted_cum[] = {-1, 2, 2, 3, 4, 4, 5, 5, 7, 7, 9}
orig_index[] = {8, 2, 4, 5, 3, 7, 1, 9, 6, 11, 10}
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1}
Assume k = 5.
We start at i = 1, where the current element = -1. We skip this to i=2 for
illustrative purpose.
For i = 2, the current element = 2.
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j] is j = 9. For j >= 9, we know that the
smallest index is min_index[9] = 6, and the largest index is max_index[9] =
11. Therefore, no doubt the maximum range when i = 2 must be 11 - 2 = 7.
Clearly, we need the max_index array as well.
Formally, the max range for sorted_cum[i] could be expressed in the
following equation:
max_range[i] = max(max_index[j], orig_index[i]) - min(min_index[j], orig_
index[i])
Then, the answer could be found as:
max(max_range[i]), for all i's.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

和
min_

【在 i****d 的大作中提到】
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
: index数组了。 O(n)
avatar
r*e
39 楼
1. step 1, 不明白为什么要用hash_map
2. step 4 的运行时间是多少呀， n^2 ？
for (int i=0; ifind all a[j] and select the min_index
}
请大牛指点一下。 谢谢

和
min_

【在 m******m 的大作中提到】
:
: 借助sum数组
: sum[i] = SUM{ a[i] | i = 0~i}
: 1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
: i的值。这样遇到相同的就说明sum[i] == sum[j], j: conflit。O(n)
: 2. 1)还是计算sum[i]。O(n)
: 2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
: 3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
: 素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
avatar
i*d
40 楼
基本思路是这样：
既然要求subarray的sum>=k，也就是说，要找 max {j-i | sum[i+1...j]>=k}
所以就遍历i，找同时满足这俩条件的j
1. sum[i+1...j]>=k。如果对sum数组排序了，就可以binary search找sum[j]<=sum[i]
-k就可以了
2. 满足第一个条件的下标j里面，我们要挑个最小的(下标)。因为已经对sum数组排序
了，假设我们找到了　*刚好*　满足第一个条件的j, 那么在排序好的sum数组中，在
sum[j]之前的都也满足第一个条件 (已经排序了。。。)
所以动机就是，我们为每个排序好的sum[j]，维持一个在sum[j]之前的最小下标就可以了

【在 S****z 的大作中提到】
: 谁来解析一下为什么得先求这个最小下标，思路是啥？
: 然后后面的为每个i找j怎么就是O(nlgn)了？
:
: 【4
: (2
: =
avatar
c*t
41 楼
赞！ 同意要max index。
但min index应该从左往右算。我原来的是对的。max index从右往左.

【在 i**********e 的大作中提到】
: Your ideas are mostly right, however you missed one important observation. To
: determine the largest range, the max_index array (not just the min_index
: array) is needed too.
: I give an example:
: A[] = {5, -3, 2, -2, 1, 4, -3, -5, 6, 4, -2}
: cum[] = {5, 2, 4, 2, 3, 7, 4, -1, 5, 9, 7}
: sorted_cum[] = {-1, 2, 2, 3, 4, 4, 5, 5, 7, 7, 9}
: orig_index[] = {8, 2, 4, 5, 3, 7, 1, 9, 6, 11, 10}
: min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
: max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1}
avatar
i*d
42 楼
你说的min_index跟我的说的不是一个东西。。。。

To

【在 i**********e 的大作中提到】
: Your ideas are mostly right, however you missed one important observation. To
: determine the largest range, the max_index array (not just the min_index
: array) is needed too.
: I give an example:
: A[] = {5, -3, 2, -2, 1, 4, -3, -5, 6, 4, -2}
: cum[] = {5, 2, 4, 2, 3, 7, 4, -1, 5, 9, 7}
: sorted_cum[] = {-1, 2, 2, 3, 4, 4, 5, 5, 7, 7, 9}
: orig_index[] = {8, 2, 4, 5, 3, 7, 1, 9, 6, 11, 10}
: min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
: max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1}
avatar
S*z
43 楼

i]
排了序之后，对sum[i+1,...j]来说,j在i后面应该是sum[j]比sum[i]大啊
比如说sum[i]处刚好是0，sum[i+1,...j]刚好是K，那么sum[j]就是K
那么怎么可能找到你说的 K = sum[j] <= sum[i]-K = 0-K = -K?
那岂不是sum[i+1,...j]这个被miss了？
以了

【在 i****d 的大作中提到】
: 基本思路是这样：
: 既然要求subarray的sum>=k，也就是说，要找 max {j-i | sum[i+1...j]>=k}
: 所以就遍历i，找同时满足这俩条件的j
: 1. sum[i+1...j]>=k。如果对sum数组排序了，就可以binary search找sum[j]<=sum[i]
: -k就可以了
: 2. 满足第一个条件的下标j里面，我们要挑个最小的(下标)。因为已经对sum数组排序
: 了，假设我们找到了　*刚好*　满足第一个条件的j, 那么在排序好的sum数组中，在
: sum[j]之前的都也满足第一个条件 (已经排序了。。。)
: 所以动机就是，我们为每个排序好的sum[j]，维持一个在sum[j]之前的最小下标就可以了
avatar
J*a
44 楼
Based on ibread's method, I think this is easy to understand, welcome any
comments.
Example: [-2, 2, -1, 3, -6] and k=3
For step 2
1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
3)给排好序的 arrary, every i , sum[i]-k; O(n)
(in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
sumnew)
Sumnew=[(-7,4),(-5,0),(-4,2),(-3,1),(-1,3)], next step is 在sum中找 最小下
标。
4)找min-index[i]. O(n)
a=0, b=0;
Temp=n+1; (put the temp min-index, set a value>n at first)
While(aif(sumnew[a].value>=sum[b].value){
If(temp>sum[b].xiabiao) temp= sum[b].xiabiao;
b++;
}
else {
min-index[sunnew[a].xiabiao]= temp;
a++ ;
}
}//end while
So, min-index[4]=5;min-index[0]=5; min-index[2]=4;min-index[1]=4; min-index
[3]=0
5) find biggest (i-min-index[i])
avatar
s*1
45 楼
it seems that the while-loop is flawed.
Example, change the k from 3 to -100. Then "a++" will never be executed.
While-loop has no stop for that case.
And it seems that there is a missing "{" after "while()"" before "if".

【在 J****a 的大作中提到】
: Based on ibread's method, I think this is easy to understand, welcome any
: comments.
: Example: [-2, 2, -1, 3, -6] and k=3
: For step 2
: 1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
: 2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
: sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
: 3)给排好序的 arrary, every i , sum[i]-k; O(n)
: (in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
: sumnew)
avatar
b*m
46 楼
似乎现在的解法都不太完美。
ihasleetcode 的算法有点诡异。
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j]
这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
使你打错了造成了我们的误解吗？
假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
乎还是要n*n。
然后
你这里的
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
的实际物理意义是当前sorted cum array 当前对应的坐标后的元素中的原始坐标的最
小值与最大值是谁？
如此设计不知意义何在？
不太明白，求解答。
觉得要设计应该设计成
min index 对应当前坐标前面到当前坐标中原始坐标的最小值，包括当前坐标
max index 对应当前坐标后面中原始坐标的最大值，也包括当前坐标。
虽然两者都考虑当前元素的原始坐标，但是显然是不会重复的。
然后当我们找到 一个i 对应的前面的满足不等式的临界值的时候，我们该做的就是直
接用对应的max index-min index 就能得到最大的range
还请ihasleetcode 能再详细谈谈
信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: Re: 刚电面完，分享两个题目
发信站: BBS 未名空间站 (Wed Feb 16 03:13:53 2011, 美东)
Your ideas are mostly right, however you missed one important observation.
To
determine the largest range, the max_index array (not just the min_index
array) is needed too.
I give an example:
A[] = {5, -3, 2, -2, 1, 4, -3, -5, 6, 4, -2}
cum[] = {5, 2, 4, 2, 3, 7, 4, -1, 5, 9, 7}
sorted_cum[] = {-1, 2, 2, 3, 4, 4, 5, 5, 7, 7, 9}
orig_index[] = {8, 2, 4, 5, 3, 7, 1, 9, 6, 11, 10}
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
Assume k = 5.
We start at i = 1, where the current element = -1. We skip this to i=2 for
illustrative purpose.
For i = 2, the current element = 2.
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j] is j = 9. For j >= 9, we know that the
smallest index is min_index[9] = 6, and the largest index is max_index[9] =
11. Therefore, no doubt the maximum range when i = 2 must be 11 - 2 = 7.
Clearly, we need the max_index array as well.
Formally, the max range for sorted_cum[i] could be expressed in the
following equation:
max_range[i] = max(max_index[j], orig_index[i]) - min(min_index[j], orig_
index[i])
Then, the answer could be found as:
max(max_range[i]), for all i's.
解法2
下面的括号没打对，明天再仔细研究下
似乎应该可以实现nlogn
发信人: Jianna (jin), 信区: JobHunting
标 题: Re: 刚电面完，分享两个题目
发信站: BBS 未名空间站 (Thu Feb 17 16:07:54 2011, 美东)
Based on ibread's method, I think this is easy to understand, welcome any
comments.
Example: [-2, 2, -1, 3, -6] and k=3
For step 2
1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
3)给排好序的 arrary, every i , sum[i]-k; O(n)
(in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
sumnew)
Sumnew=[(-7,4),(-5,0),(-4,2),(-3,1),(-1,3)], next step is 在sum中找 最小下
标。
4)找min-index[i]. O(n)
a=0, b=0;
Temp=n+1; (put the temp min-index, set a value>n at first)
While(aif(sumnew[a].value>=sum[b].value){
If(temp>sum[b].xiabiao) temp= sum[b].xiabiao;
b++;
}
else {
min-index[sunnew[a].xiabiao]= temp;
a++ ;
}
}//end while
So, min-index[4]=5;min-index[0]=5; min-index[2]=4;min-index[1]=4; min-index
[3]=0
5) find biggest (i-min-index[i])
avatar
J*a
47 楼
是的， 在 while 后面需要{
and also temp=n+1=6,
So, min-index[4]=6;min-index[0]=6;
and also if i- min-index[i]<=0, 则找不到这样的subarry.
In this example,subarry is from min-index[3] +1 to 3. 这里是subarry[1 to 3]
, 即2, -1, 3
And I also think the step 3 may be not necessary, because sumnew[a].value=
sum[a].value-3

【在 s*********1 的大作中提到】
: it seems that the while-loop is flawed.
: Example, change the k from 3 to -100. Then "a++" will never be executed.
: While-loop has no stop for that case.
: And it seems that there is a missing "{" after "while()"" before "if".
avatar
i*e
48 楼
我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumulative
array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
would miss including the first element in the contiguous sum array.
2) For each i from 0 to n, we use binary search to find the smallest j that
satisfies the condition cum[i]+k >= cum[j], where cum[] array is the sorted
cumulative array. Why? We must satisfy the invariant where cum[i...j] >= k.
Note that cum[i...j] = cum[j] - cum[i-1]. If we found the smallest j(min_j)
such that cum[i...j] >= k, then any j >= min_j MUST also satisfy the
invariant, because cum[j] >= cum[min_j] for any j >= min_j, since cum[]
array is sorted.
3) Earlier I mentioned that I need to keep track of minIndex and maxIndex. In fact maxIndex is sufficient. We need only find cum[i...j], where j >= i. If j < i it is invalid.
4) It is quite tricky to implement the binary search without the correct invariant. Consult Programming Pearls Column 9 for the implementation details.
5) As for ibread's method, I believe his method is correct but I do not quite understand what it means by his minIndex. Could you please post your working code? It might be easier to understand through your code.
struct Cumulative {
int val;
int origIndex;
bool operatorreturn ((val == b.val) ? origIndex < b.origIndex : val < b.val);
}
};
int binarySearchGreaterThan(int t, Cumulative A[], int n) {
int l = -1;
int u = n;
while (l+1 != u) {
// invariant: A[l] < t && A[u] >= t && l < u
int m = l + (u - l) / 2;
assert(m >= 0 && m <= n-1);
if (A[m].val < t)
l = m;
else
u = m;
}
// A[l] < t && A[u] >= t && l+1 == u
assert(u >= 0 && u <= n);
if (u == n)
return -1;
else
return u;
}
struct Range {
int start;
int end;
Range() : start(0), end(-1) {}
};
Range maxSizeSubarraySumGreaterThan(int k, int A[], int n) {
Cumulative *cum = new Cumulative[n+1];
cum[0].val = 0;
cum[0].origIndex = 0;
for (int i = 1; i < n+1; i++) {
cum[i].val = cum[i-1].val + A[i-1];
cum[i].origIndex = i;
}
sort(cum, cum+n+1);

int *maxIndex = new int[n+1];
int maxIndexSoFar = INT_MIN;
for (int i = n; i >= 0; i--) {
if (cum[i].origIndex > maxIndexSoFar)
maxIndexSoFar = cum[i].origIndex;
maxIndex[i] = maxIndexSoFar;
}
Range maxRange;
for (int i = 0; i < n+1; i++) {
int min_j = binarySearchGreaterThan(cum[i].val+k, cum, n+1);
if (min_j == -1)
break;
int range = maxIndex[min_j] - cum[i].origIndex;
if (range > maxRange.end - maxRange.start) {
maxRange.start = cum[i].origIndex;
maxRange.end = maxIndex[min_j];
}
}
delete[] cum;
delete[] maxIndex;
maxRange.end--;
if (maxRange.start > maxRange.end) {
maxRange.start = maxRange.end = -1;
}
return maxRange;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 b*m 的大作中提到】
: 似乎现在的解法都不太完美。
: ihasleetcode 的算法有点诡异。
: Using binary search, we found the smallest j that satisfies the condition
: sorted_cum[i]+k >= sorted_cum[j]
: 这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
: 使你打错了造成了我们的误解吗？
: 假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
: 然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
: 件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
: 乎还是要n*n。
avatar
w*p
49 楼
终于有人和我想的差不多
第二题O（n) time 和O(n) spance 就可以了
不过要注意K>0和K<0算法有些不一样。
case 1: K>=0
/*working on array of sum(i)
/* sum(i) defintion: sum of all element from 0 to i. ex: sum(2) = sum(1)
+ number[2] = number[0]+ number[1]+ number [2] */
1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
2. find the max sum which index is j O(n) time
3. check from left side of sum(j), find the min of sum array which index is
k
4 .If the min >= 0, all number array [0-j] are the sub array
if the min < 0 , number array[k+1 - j] are the sub array
case 1: K<0 .....similar
avatar
f*w
50 楼

...
1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
2. find the max sum which index is j O(n) time
~~~~~~~~This search need to be from right to left, in case
there are equal maximum sum(j)
3. check from left side of sum(j), find the min of sum array which index is
k
~~~~~~~~~Here need to check condition sum[j] - sum[k] >= K,
right?
4 .If the min >= 0, all number array [0-j] are the sub array
if the min < 0 , number array[k+1 - j] are the sub array

【在 w********p 的大作中提到】
: 终于有人和我想的差不多
: 第二题O（n) time 和O(n) spance 就可以了
: 不过要注意K>0和K<0算法有些不一样。
: case 1: K>=0
: /*working on array of sum(i)
: /* sum(i) defintion: sum of all element from 0 to i. ex: sum(2) = sum(1)
: + number[2] = number[0]+ number[1]+ number [2] */
: 1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
: 2. find the max sum which index is j O(n) time
: 3. check from left side of sum(j), find the min of sum array which index is
avatar
i*e
51 楼
I forgot to mention the sorting part.
You need to sort the sum array to apply binary search.
I am not convinced your method without sorting works.
Prove your method works by posting your code.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

1)
space
is

【在 w********p 的大作中提到】
: 终于有人和我想的差不多
: 第二题O（n) time 和O(n) spance 就可以了
: 不过要注意K>0和K<0算法有些不一样。
: case 1: K>=0
: /*working on array of sum(i)
: /* sum(i) defintion: sum of all element from 0 to i. ex: sum(2) = sum(1)
: + number[2] = number[0]+ number[1]+ number [2] */
: 1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
: 2. find the max sum which index is j O(n) time
: 3. check from left side of sum(j), find the min of sum array which index is
avatar
s*3
52 楼
Great post. Thanks.
For 2), it seems that it should be cum[j] >= cum[i]+k.

）。
cumulative
Using
.j
that
sorted

【在 i**********e 的大作中提到】
: 我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
: 基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
: 1) First, we store the contiguous sum from the first element to a cumulative
: array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
: the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
: ] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
: define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
: would miss including the first element in the contiguous sum array.
: 2) For each i from 0 to n, we use binary search to find the smallest j that
: satisfies the condition cum[i]+k >= cum[j], where cum[] array is the sorted
avatar
f*w
53 楼
好难得题目阿 换我也肯定被秒杀了
avatar
m*k
54 楼
for 1, simply check dup key is not enough, which only works for case when
the wanted subarry starts from non 0 index,
try X=[0,1,2] or X=[3, -3, 5] , need check if contains key == 0 too
avatar
i*e
55 楼
Yes, your observation is right.
This common mistake is pointed out in my post at #37.
The simple dup check key is able to work with just a simple
modification:
You would need a sum array of size n+1 with the first element in the sum
array set to 0.
For example, X = [0,1,2],
sum = [0, 0, 1, 3].
X = [3, -3, 5],
sum = [0, 3, 0, 5].
This is because X[i...j] = sum[j] - sum[i-1].
X[0] (The first element) will be missed if you do not start from 0 in the
sum array.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 m*****k 的大作中提到】
: for 1, simply check dup key is not enough, which only works for case when
: the wanted subarry starts from non 0 index,
: try X=[0,1,2] or X=[3, -3, 5] , need check if contains key == 0 too
avatar
i*e
56 楼
Yes you are right, the below invariant is incorrect:
sorted_cum[i]+k >= sorted_cum[j]
It should be the other way around, just like what smallbug123 pointed out:
sorted_cum[i]+k <= sorted_cum[j] , i <= j
Thanks for the correction. I've corrected the mistake in my post at #37.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 b*m 的大作中提到】
: 似乎现在的解法都不太完美。
: ihasleetcode 的算法有点诡异。
: Using binary search, we found the smallest j that satisfies the condition
: sorted_cum[i]+k >= sorted_cum[j]
: 这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
: 使你打错了造成了我们的误解吗？
: 假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
: 然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
: 件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
: 乎还是要n*n。
avatar
Z*4
57 楼
用4吧。。

,
0?

【在 w*****k 的大作中提到】
:
: 和
: min_
: 能再详细解释下这句话吗
: min_index[i]是比sum[i]小的元素中的最小的下标。
: 以上面帖子中的例子为例，排序后的sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,
: 3)]
: 排序后的sum[0]=-4, 比sum[0]小的没有，默认min_index[0]=4 还是min_index[0] = 0?
avatar
g*k
58 楼
Your solution is actually the same as ibread's solution.
in ibread's solutio's last step, j starts from n to 0, so binary search
in the sorted cum array s.t. cum[i]<= cum[j]-k. Once you find i, you just
get the smallest index by min_index[i].
min_index[i]= min{k | cum[k]j-min_index[i] is the length of the subarray starting at min_index[i]+1.

我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumulative
array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
would miss including the first element in the contiguous sum array.
2) Then we sort the cum[] array, which is used to apply Binary Search in 3).
3) For each i from 0 to n, we use binary search to find the smallest j that
satisfies the condition cum[i]+k <= cum[j+1], where cum[] array is the
sorted
cumulative array. Why? We must satisfy the invariant where A[i...j] >= k.
Note that A[i...j] = cum[j+1] - cum[i]. If we found the smallest j(min_j)
such that A[i...j] >= k, then any j >= min_j MUST also satisfy the
invariant, because cum[j] >= cum[min_j] for any j >= min_j and cum[]
array is sorted.
4) Earlier I mentioned that I need to keep track of minIndex and maxIndex.
In fact maxIndex is sufficient. We need only find cum[i...j], where j >= i.
If j < i it is invalid.
5) It is quite tricky to implement the binary search without the correct
invariant. Consult Programming Pearls Column 9 for the implementation
details.
6) As for ibread's method, I believe his method is correct but I do not
quite understand what it means by his minIndex. Could you please post your
working code? It might be easier to understand through your code.
struct Cumulative {
int val;
int origIndex;
bool operatorreturn ((val == b.val) ? origIndex < b.origIndex : val < b.val);
}
};
int binarySearchGreaterThan(int t, Cumulative A[], int n) {
int l = -1;
int u = n;
while (l+1 != u) {
// invariant: A[l] < t && A[u] >= t && l < u
int m = l + (u - l) / 2;
assert(m >= 0 && m <= n-1);
if (A[m].val < t)
l = m;
else
u = m;
}
// A[l] < t && A[u] >= t && l+1 == u
assert(u >= 0 && u <= n);
if (u == n)
return -1;
else
return u;
}
struct Range {
int start;
int end;
Range() : start(0), end(-1) {}
};
Range maxSizeSubarraySumGreaterThan(int k, int A[], int n) {
Cumulative *cum = new Cumulative[n+1];
cum[0].val = 0;
cum[0].origIndex = 0;
for (int i = 1; i < n+1; i++) {
cum[i].val = cum[i-1].val + A[i-1];
cum[i].origIndex = i;
}
sort(cum, cum+n+1);

int *maxIndex = new int[n+1];
int maxIndexSoFar = INT_MIN;
for (int i = n; i >= 0; i--) {
if (cum[i].origIndex > maxIndexSoFar)
maxIndexSoFar = cum[i].origIndex;
maxIndex[i] = maxIndexSoFar;
}
Range maxRange;
for (int i = 0; i < n+1; i++) {
int min_j = binarySearchGreaterThan(cum[i].val+k, cum, n+1);
if (min_j == -1)
break;
int range = maxIndex[min_j] - cum[i].origIndex;
if (range > maxRange.end - maxRange.start) {
maxRange.start = cum[i].origIndex;
maxRange.end = maxIndex[min_j];
}
}
delete[] cum;
delete[] maxIndex;
maxRange.end--;
if (maxRange.start > maxRange.end) {
maxRange.start = maxRange.end = -1;
}
return maxRange;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 i**********e 的大作中提到】
: 我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
: 基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
: 1) First, we store the contiguous sum from the first element to a cumulative
: array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
: the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
: ] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
: define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
: would miss including the first element in the contiguous sum array.
: 2) For each i from 0 to n, we use binary search to find the smallest j that
: satisfies the condition cum[i]+k >= cum[j], where cum[] array is the sorted
avatar
P*l
59 楼
弱弱地问，subarray一定是连续的吗？
avatar
i*e
60 楼
对，是连续的。
如果不是连续的话 貌似难度很大
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 P**l 的大作中提到】
: 弱弱地问，subarray一定是连续的吗？
相关阅读
咨询一下体温调节的分子机制想换个实验室做博后Puncturing the Myth (ZT) from The Scientist流式细胞仪 使用DNase处理peoplem的口气很臭啊Lehninger principles of biochemistry 第五版习题答案请教NATURE投稿问题第二届青年千人申请有没有在weizmann的book help靠，生产地沟油的名字都这么拽 (转载)台湾2010年寿命调查：中医师比牙医及西医短命6、7岁---转载有人如果拿藿香正气丸举例肘子 对 青蒿素，youyou 没反应了？求几篇全文，哪位好心人能找到吧？用pVAX构建的真核表达载体能在这些细胞里表达吗？生物版太不够意思了请问一下这样的publication，回国的话申请什么职位合适因牛胰岛素和青蒿素获得院士的人数能不能互相挂二作增加论文数量？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。