S**Y
发帖数: 136 | 1 How do you find sequences of consequtive integers in a list that add to a pa
rticular number. |
r****o
发帖数: 1950 | 2 看不懂，能说仔细一点吗?
pa
【在 S**Y 的大作中提到】
: How do you find sequences of consequtive integers in a list that add to a pa
: rticular number.
|
m*****f
发帖数: 1243 | 3 say a1, a2, a3, ....an:
compute the sum one by one and list them as a new list
a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
this will take O(n).
now the question becomes find two numbers a, b in this new list, that
a - b = that particular number, which is a typical 2sum problem solved
in O(n)
Possible follow-up: if the word "consequtive" is removed, then it becomes a
0/1 knapsack problem, could be solved by dp. |
r****o
发帖数: 1950 | 4 能不能讲讲题目里面add to a particular number是啥意思？
a
【在 m*****f 的大作中提到】
: say a1, a2, a3, ....an:
: compute the sum one by one and list them as a new list
: a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
: this will take O(n).
: now the question becomes find two numbers a, b in this new list, that
: a - b = that particular number, which is a typical 2sum problem solved
: in O(n)
: Possible follow-up: if the word "consequtive" is removed, then it becomes a
: 0/1 knapsack problem, could be solved by dp.
|
m*****f
发帖数: 1243 | 5 sum = a particular number?
【在 r****o 的大作中提到】
: 能不能讲讲题目里面add to a particular number是啥意思？
:
: a
|
r****o
发帖数: 1950 | 6 呵呵，不好意思这才明白。
【在 m*****f 的大作中提到】
: sum = a particular number?
|
r****o
发帖数: 1950 | 7
这里是要考虑任意两个numbers吧，是不是O(n^2)?
a
【在 m*****f 的大作中提到】
: say a1, a2, a3, ....an:
: compute the sum one by one and list them as a new list
: a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
: this will take O(n).
: now the question becomes find two numbers a, b in this new list, that
: a - b = that particular number, which is a typical 2sum problem solved
: in O(n)
: Possible follow-up: if the word "consequtive" is removed, then it becomes a
: 0/1 knapsack problem, could be solved by dp.
|
m*****f
发帖数: 1243 | 8 hash table ah
【在 r****o 的大作中提到】
:
: 这里是要考虑任意两个numbers吧，是不是O(n^2)?
: a
|
r****o
发帖数: 1950 | 9 u r right
【在 m*****f 的大作中提到】
: hash table ah
|
S**Y
发帖数: 136 | 10 你理解错题意了吧
题目是说，consecutive的integers,不是连续的序号
比如:
2 4 7 3 10 4 8
那这个应该是7+8 = 15
a
【在 m*****f 的大作中提到】
: say a1, a2, a3, ....an:
: compute the sum one by one and list them as a new list
: a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
: this will take O(n).
: now the question becomes find two numbers a, b in this new list, that
: a - b = that particular number, which is a typical 2sum problem solved
: in O(n)
: Possible follow-up: if the word "consequtive" is removed, then it becomes a
: 0/1 knapsack problem, could be solved by dp.
|
|
|
m*****f
发帖数: 1243 | 11 @@...then it's much more easier. just sort.
【在 S**Y 的大作中提到】
: 你理解错题意了吧
: 题目是说，consecutive的integers,不是连续的序号
: 比如:
: 2 4 7 3 10 4 8
: 那这个应该是7+8 = 15
:
: a
|
S**Y
发帖数: 136 | 12 if you sort you will lose the order
不再是 increasing的了
【在 m*****f 的大作中提到】
: @@...then it's much more easier. just sort.
|
m*****f
发帖数: 1243 | 13 en, 那我不会
【在 S**Y 的大作中提到】
: if you sort you will lose the order
: 不再是 increasing的了
|
r****o
发帖数: 1950 | 14 那不就是任意几个数的和等于15吗？
加法跟consecutive没关系吧？
0-1 knapsack?
【在 S**Y 的大作中提到】
: 你理解错题意了吧
: 题目是说，consecutive的integers,不是连续的序号
: 比如:
: 2 4 7 3 10 4 8
: 那这个应该是7+8 = 15
:
: a
|
h**k
发帖数: 3368 | 15 能详细讲讲么？怎么用hash table来做？
【在 m*****f 的大作中提到】
: hash table ah
|
k***e
发帖数: 556 | 16 哎 在问之前能否先阅读下基本的书籍。我在板上推荐programming pearls好几次了
pa
【在 S**Y 的大作中提到】
: How do you find sequences of consequtive integers in a list that add to a pa
: rticular number.
|
r****o
发帖数: 1950 | 17 programming peals哪章讲了这个问题啊
【在 k***e 的大作中提到】
: 哎 在问之前能否先阅读下基本的书籍。我在板上推荐programming pearls好几次了
:
: pa
|
k***e
发帖数: 556 | 18 这是一个习题
【在 r****o 的大作中提到】
: programming peals哪章讲了这个问题啊
|
H*M
发帖数: 1268 | 19 他也没看清楚题呵呵
【在 r****o 的大作中提到】
: programming peals哪章讲了这个问题啊
|
k***e
发帖数: 556 | 20 晕 这个楼主也不说清楚点
那个consecutive我还以为是说sequence contiguous
he should say find a subsequence in the array that is continuous increasing
【在 H*M 的大作中提到】
: 他也没看清楚题呵呵
|
|
|
k***e
发帖数: 556 | 21 ok, my fault
i misunderstand the problem
suppose the problem is: given an array of pos ints, find a subseqence (may
not be continuous in the idxes), that is continuous integers that sum to a
certain value)
1) for each a[i] in the array, find idxUp > i such that a[idxUp] = a[i] + 1
idxDown < i such that a[idxDown] = a[i] - 1, note that the idxUp is the one
who is closest to i (similar to find idxDown)
2) thus from any idx, we know where is the next a[idx]+1, now we need to get
the length of the c
【在 r****o 的大作中提到】
: programming peals哪章讲了这个问题啊
|
H*M
发帖数: 1268 | 22 yeah
max inreseacing sub sequence, max in terms of sum instead of lenth
increasing
【在 k***e 的大作中提到】
: 晕 这个楼主也不说清楚点
: 那个consecutive我还以为是说sequence contiguous
: he should say find a subsequence in the array that is continuous increasing
|
r****o
发帖数: 1950 | 23 没看明白，我怎么觉得这个问题就是0-1 knapsack啊？
1
one
get
=
【在 k***e 的大作中提到】
: ok, my fault
: i misunderstand the problem
: suppose the problem is: given an array of pos ints, find a subseqence (may
: not be continuous in the idxes), that is continuous integers that sum to a
: certain value)
: 1) for each a[i] in the array, find idxUp > i such that a[idxUp] = a[i] + 1
: idxDown < i such that a[idxDown] = a[i] - 1, note that the idxUp is the one
: who is closest to i (similar to find idxDown)
: 2) thus from any idx, we know where is the next a[idx]+1, now we need to get
: the length of the c
|
k***e
发帖数: 556 | 24 that can be solved in linear time instead of using dp
【在 r****o 的大作中提到】
: 没看明白，我怎么觉得这个问题就是0-1 knapsack啊？
:
: 1
: one
: get
: =
|
m******r
发帖数: 61 | 25 真难
pa
【在 S**Y 的大作中提到】
: How do you find sequences of consequtive integers in a list that add to a pa
: rticular number.
|
