d********w
发帖数: 363 | 1 First, we can consider 2 numbers, which is O(n) time. We can use 2 two
pointers to process the sorted array or use hashtable to find whether T-cur
in it.
If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
"When the integers are in the range [−u ... u], 3SUM can be solved in
time O(n + u lg u) by representing S as a bit vector and performing a
convolution using FFT." but it is hard to follow.
How about number extends to k? | g*********s
发帖数: 1782 | 2 subset sum, npc.
T-cur
http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
in
【在 d********w 的大作中提到】
: First, we can consider 2 numbers, which is O(n) time. We can use 2 two
: pointers to process the sorted array or use hashtable to find whether T-cur
: in it.
: If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
: "When the integers are in the range [−u ... u], 3SUM can be solved in
: time O(n + u lg u) by representing S as a bit vector and performing a
: convolution using FFT." but it is hard to follow.
: How about number extends to k?
| z****o
发帖数: 78 | 3 When value range is limited, it is a DP-able problem. | j********x
发帖数: 2330 | 4 k is a fixed number... subset sum considers the case that k is not fixed,
which forces to explore all possible combinations.
I believe the complexity is n^(k-1) just guess
【在 g*********s 的大作中提到】
: subset sum, npc.
:
: T-cur
: http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
: in
| P********l
发帖数: 452 | 5 http://www.sureinterview.com/shwqst/98001
At least, it can be done within n^(k/2). Seems still room to improve. |
|
