由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - [Algo] k numbers in array of n numbers sum to T
相关主题
奉献phone screen真题两枚老问题了,网上竟然找不到答案
find subset that sum up to given number问一个编程题
how do you find x number of items in an array sum up to K?这个问题有什么快速的方法..
请教一个问题,发两个包子。求助:一道careercup的算法题
Extension problem of finding intersection of two sorted arrayAmazon二面结束,求BLESS
问两道微软题问一个给定的array 和一个sum value,找最小sub-array,谢谢
面试题总结(2) - Two/Three pointers一个面试题
LinkedIn onsite一道题问个算法题,修改版
相关话题的讨论汇总
话题: numbers话题: algo话题: array话题: sum话题: time
进入JobHunting版参与讨论
1 (共1页)
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.
1 (共1页)
进入JobHunting版参与讨论
相关主题
问个算法题,修改版Extension problem of finding intersection of two sorted array
怎么找均值相等的Two Partition of an array问两道微软题
问个google面试题面试题总结(2) - Two/Three pointers
partition array problemLinkedIn onsite一道题
奉献phone screen真题两枚老问题了,网上竟然找不到答案
find subset that sum up to given number问一个编程题
how do you find x number of items in an array sum up to K?这个问题有什么快速的方法..
请教一个问题,发两个包子。求助:一道careercup的算法题
相关话题的讨论汇总
话题: numbers话题: algo话题: array话题: sum话题: time