Hi,

Sorry if this question has been asked before but I need some help on this as I am stuck on this for more than one year. The problem is as follows -

I have three arrays A,B,C of same size let say n and I need to find out all possible (i,j,k) such that A[i]+B[j]=C[k]. And we

need to find this in O(n^2) complexity for which I found one solution like

Step 1:

Add all A[i]+B[j] as the key and (i,j) as values in a hash table.This gives n^2 no of keys and values.

Step 2:

Traverse for all C[k] and probe the hash table.If mach found (i,j,k) is one pair and so on.

This looks like an O(n^2) solution.But can it be done better or at least O(n^2) in some different approach ?

Regards,

Arka