algorithm - Find 3 elements in each of 3 arrays that sum to a given value -

let , b, c 3 arrays of n elements each. find algorithm determining whether there exist a in a, b in b, c in c such a+b+c = k.

i have tried following algorithm, takes o(n²):

1. sort 3 arrays. - o(n log n)

2. temporary array h = k - (a+b) - o(n)

3. for every h, find c' in b such c' = h - b[i] - o(n)

4. search c' in c using binary search - o(log n)

total = o(n log n) + o(n) + o(n² log n)

can solve in o(n log n)?

suppose there existed solution s problem in o(n lg n) time.

i show instance of 3sum, array of length n, linear-time reduces problem.

given 3sum instance array s of length n, define arrays a = b = c = s, o(n) operation. use s(a, b, c, 0) determine whether there exist indices a,b,c arrays a,b,c, respectively, such a[a] + b[b] + c[c] = 0 in o(n lg n) time. since each array equal s, same values a,b,c satisfy 3sum's s[a] + s[b] + s[c] = 0.

unless you're publish big, doubt there can such fast algorithm problem, @ least hard 3sum (you can show reduction in opposite direction work, too).

edit: make above paragraph clear, linear-time reduction 3sum proves op's problem $\omega(n^{1.5})$.