| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Asked in a Finance Company Interview :
Given three unsorted arrays A,B and C, the task is to find three elements a,b,c from the three arrays such that a+b=c.
Can it be done in O(nlogn)?
Suppose the arrays are given as sorted, then can it be done in linear time?
Currently the best I have is that if the maximal value of an element in one of the arrays is M, then we can find all possible sums of arrays A, B in
using fft, and then sort array C in 
and find a common value in 
.
I might be missing something clear.
It appears that this problem is reducible to 3SUM. Therefore, it is unsolvable in less than O(n²) time if the values of the elements are unbounded.
The problem looks similar enough to 3SUM problem, and for its general case, there's no known solution in
: a deterministic solution better than O(n2) was invented only recently, in 2014.
Note that the Wikipedia page mentions the FFT solution presented above by Noam527 when the array elements are bounded integers.