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

Question

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?

Answer 1

Sounds like a homework question...

If you can find two values that sum to N but you want to extend the search to three values, couldn't you, for each value M in the set, look for two values that sum to (N - M)? If you can find two values that sum to a specific value in O(log N) time, then that will be O(N log N).

Answer 2

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

Answer 3

I think this is just the subset sum problem

If so, it is NP-Complete.

EDIT: Never mind, it is 3sum, as stated in another answer.