Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
939 views
in Technique[技术] by (71.8m points)

algorithm - O(NlogN) finding 3 numbers that have a sum of any arbitrary T in an array

Given an array A of integers, find any 3 of them that sum to any given T.

I saw this on some online post, which claims it has a O(NlogN) solution.

For 2 numbers, I know hashtable could help for O(N), but for 3 numbers, I cannot find one.

I also feel this problem sounds familar to some hard problems, but cannot recall the name and therefore cannot google for it. (While the worst is obviously O(N^3), and with the solution to 2 numbers it is really O(N^2) )

It does not really solve anything in the real world, just bugs me..

Any idea?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I think your problem is equivalent to the 3SUM problem.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...