H*M
发帖数: 1268 | 1 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想不出什么天外飞仙的算法达到O(nlgn)
谁有点idea? |
h*******e
发帖数: 225 | 2 你听错题了吧
up
【在 H*M 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?
|
n******r
发帖数: 1247 | 3 答案是没有这样的算法
up
【在 H*M 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?
|
H*M
发帖数: 1268 | 4 是在别地方烤来的.
那最快的算法是多少?
【在 h*******e 的大作中提到】
: 你听错题了吧
:
: up
|
c*****g
发帖数: 1137 | 5 easy to get n^2, not sure about nlogn
【在 H*M 的大作中提到】
: 是在别地方烤来的.
: 那最快的算法是多少?
|
w********p
发帖数: 948 | 6 我也见过这道题。我相信我的算法是nlgn, 但是有些细节不知道怎么写成sudocode
【在 h*******e 的大作中提到】
: 你听错题了吧
:
: up
|
H*M
发帖数: 1268 | 7 你说说吧
据说无解?
【在 w********p 的大作中提到】
: 我也见过这道题。我相信我的算法是nlgn, 但是有些细节不知道怎么写成sudocode
|
m********0
发帖数: 2717 | 8 O(n^2) is trivial .
貌似前段时间Quant版讨论过，有人给出paper link
目前的最好算法就是 O(nlogn)。
记不太清楚了。 找了半天没找到。
up
【在 H*M 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 想不出什么天外飞仙的算法达到O(nlgn)
: 谁有点idea?
|
g*******y
发帖数: 1930 | 9 本版就讨论过，我发的帖子问的。
结论是不可能，结论是有paper证明的！！！ |
g*******y
发帖数: 1930 | 10 本版就讨论过，我发的帖子问的。
结论是不可能，结论是有paper证明的！！！ |
|
|
h*******e
发帖数: 225 | 11 找不到就对了，因为3SUM目前没有人知道o(n^2)的算法，只有在一些特定的model下有
稍微快一点的。
【在 m********0 的大作中提到】
: O(n^2) is trivial .
: 貌似前段时间Quant版讨论过，有人给出paper link
: 目前的最好算法就是 O(nlogn)。
: 记不太清楚了。 找了半天没找到。
:
: up
|
H*M
发帖数: 1268 | 12 ft..我说在哪见过..
那如果是两个,是不是就是hash后,直接过一遍?还是有什么天外飞仙的方法?
【在 g*******y 的大作中提到】
: 本版就讨论过，我发的帖子问的。
: 结论是不可能，结论是有paper证明的！！！
|
m********0
发帖数: 2717 | 13 那就是我记错了。
一个类似的题目在quant版讨论过，
比这个题目复杂。
【在 h*******e 的大作中提到】
: 找不到就对了，因为3SUM目前没有人知道o(n^2)的算法，只有在一些特定的model下有
: 稍微快一点的。
|
m********0
发帖数: 2717 | 14 link to the paper?
【在 g*******y 的大作中提到】
: 本版就讨论过，我发的帖子问的。
: 结论是不可能，结论是有paper证明的！！！
|
g*******y
发帖数: 1930 | 15 忘了，记得是篇会议文，还记得貌似是Fairylander给的link
【在 m********0 的大作中提到】
: link to the paper?
|
l***i
发帖数: 1309 | 16 wikipedia search 3SUM problem. There is no better solution than O(n^2)
currently and there are a number of problems that would have a faster
solution if 3SUM has a better than O(n^2) solution, say O(nlogn). |
