由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 刚电面完,分享两个题目
相关主题
liverampOA题目Maximum Contiguous Subarray
请教个题目,求最长subarry, average < kMaximum Sum of Increasing Sequence
请教大家一道“Programming Pearls" 上面的题目请教一个facebook面试题
贡献两个Amazon的电话面试题问一道算法题largest subsequence sum <= max
请教一道题求 Maximum Subarray divide and conquer 解法
Random Array number, Find longest consecutive sequenceLeet Code, three sum closest
哪里有讲k-way merge的?merge a1,a2,..b1,b2 to a1b1a2b2..
onsite遇到的几个面试题请教一题
相关话题的讨论汇总
话题: cum话题: sum话题: min话题: index话题: array
进入JobHunting版参与讨论
1 (共1页)
v*****d
发帖数: 348
1
公司名就不说了,估计版上没几个人听说过。个人觉得挺难的,主要是以前没碰到过
给一个array, 判断是否有subarray的sum是0. 要求O(n)算法
给一个array, 给一个given number k, 给出最长的subarray的length, 这个subarray
的sum大于或等于k.要求O(nlogn)算法
被那个经典的maximal sum subarray的题误导了,一开始就没想到正点上去。都是面试
官给了hint才做出来,悲剧。。move on了
t**d
发帖数: 352
2
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
g*********s
发帖数: 1782
3
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了

i**9
发帖数: 351
4
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

v*****d
发帖数: 348
5
恩,是的。第一题前面有人贴出答案了,第二题用binary search做

【在 g*********s 的大作中提到】
: is it some high-profile startup? so what are the hints?
: the 2nd one smells still like a dp.
:
: subarray

v*****d
发帖数: 348
6
恩,是的。第一题前面有人贴出答案了,第二题提示和第一题差不多,但不用
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

g*********s
发帖数: 1782
7
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

t**d
发帖数: 352
8
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

t**d
发帖数: 352
9
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.
b******n
发帖数: 4509
10
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
相关主题
Random Array number, Find longest consecutive sequenceMaximum Contiguous Subarray
哪里有讲k-way merge的?Maximum Sum of Increasing Sequence
onsite遇到的几个面试题请教一个facebook面试题
进入JobHunting版参与讨论
j*****u
发帖数: 1133
11
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.

v*****d
发帖数: 348
12
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
b******n
发帖数: 4509
13
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

g*********s
发帖数: 1782
14
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

v*****d
发帖数: 348
15
恩,还是有问题。有高人出来讲解一下不?

【在 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

l******l
发帖数: 66
16
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.
i****d
发帖数: 35
17
借助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)
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了

Z*****Z
发帖数: 723
18
这个不错,顶一下


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)

m******m
发帖数: 19
19

借助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)
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)

i****d
发帖数: 35
20
啊对。。。。多谢指出来。。。已经改正了~


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_

相关主题
问一道算法题largest subsequence sum <= maxmerge a1,a2,..b1,b2 to a1b1a2b2..
求 Maximum Subarray divide and conquer 解法请教一题
Leet Code, three sum closest[问一道题] maximum contiguous subarray with sum >= target number
进入JobHunting版参与讨论
w*****k
发帖数: 42
21


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)

c********t
发帖数: 5706
22
我理解 应该是 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?

c********t
发帖数: 5706
23
赞, 我想不出有啥其他办法。


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)

S****z
发帖数: 666
24
谁来解析一下为什么得先求这个最小下标,思路是啥?
然后后面的为每个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?

i**********e
发帖数: 1145
25
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
i**********e
发帖数: 1145
26
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?

i**********e
发帖数: 1145
27
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)

r******e
发帖数: 80
28
1. step 1, 不明白为什么要用hash_map
2. step 4 的运行时间是多少呀, n^2 ?
for (int i=0; i find 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_

i****d
发帖数: 35
29
基本思路是这样:
既然要求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
: =

c********t
发帖数: 5706
30
赞! 同意要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}

相关主题
每次刷题都有新发现请教个题目,求最长subarry, average < k
荷兰国旗问题的扩展请教大家一道“Programming Pearls" 上面的题目
liverampOA题目贡献两个Amazon的电话面试题
进入JobHunting版参与讨论
i****d
发帖数: 35
31
你说的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}

S****z
发帖数: 666
32

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]之前的最小下标就可以了

J****a
发帖数: 15
33
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(a if(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])
s*********1
发帖数: 20
34
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)

b*m
发帖数: 34
35
似乎现在的解法都不太完美。
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(a if(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])
J****a
发帖数: 15
36
是的, 在 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".

i**********e
发帖数: 1145
37
我今天写的代码,通过了我的一些随机数据测试(与 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 operator<(const Cumulative &b) {
return ((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。

w********p
发帖数: 948
38
终于有人和我想的差不多
第二题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
f**********w
发帖数: 93
39

...
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

i**********e
发帖数: 1145
40
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

相关主题
贡献两个Amazon的电话面试题哪里有讲k-way merge的?
请教一道题onsite遇到的几个面试题
Random Array number, Find longest consecutive sequenceMaximum Contiguous Subarray
进入JobHunting版参与讨论
s*********3
发帖数: 389
41
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

f*****w
发帖数: 2602
42
好难得题目阿 换我也肯定被秒杀了
m*****k
发帖数: 731
43
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
i**********e
发帖数: 1145
44
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

i**********e
发帖数: 1145
45
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。

Z**********4
发帖数: 528
46
用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?

g*****k
发帖数: 623
47
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 operator<(const Cumulative &b) {
return ((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

P**l
发帖数: 3722
48
弱弱地问,subarray一定是连续的吗?
i**********e
发帖数: 1145
49
对,是连续的。
如果不是连续的话 貌似难度很大
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 P**l 的大作中提到】
: 弱弱地问,subarray一定是连续的吗?
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一题请教一道题
[问一道题] maximum contiguous subarray with sum >= target numberRandom Array number, Find longest consecutive sequence
每次刷题都有新发现哪里有讲k-way merge的?
荷兰国旗问题的扩展onsite遇到的几个面试题
liverampOA题目Maximum Contiguous Subarray
请教个题目,求最长subarry, average < kMaximum Sum of Increasing Sequence
请教大家一道“Programming Pearls" 上面的题目请教一个facebook面试题
贡献两个Amazon的电话面试题问一道算法题largest subsequence sum <= max
相关话题的讨论汇总
话题: cum话题: sum话题: min话题: index话题: array