Menu
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?
583
Algorithm: Given an array of length n and a sum s. Create three nested loop first loop runs from start to end (loop counter i), second loop runs from i+1 to end (loop counter j) and third loop runs from j+1 to end (loop counter k) The counter of these loops represents the index of 3 elements of the triplets.
I think your problem is equivalent to the 3SUM problem.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
