The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there are are three arrays $X,Y,Z$, and we have to find a number per array $a\in X, b\in Y, c\in Z$ such that $a+b+c=0$. Call the first variant 3SUMx1 and the second one 3SUMx3.
Given an oracle for 3SUMx3, can we solve 3SUMx1 in linear time?
One option that comes to mind is just to create 3 replicates of the input array $S$ and run: 3SUMx3($S,S,S$). However, this may return two copies of the same item. E.g. if $S$ has only two elements, 1 and -2, then the 3SUMx1 problem has no solution, but 3SUMx3($S,S,S$) will return the fake solution $(1,1,-2)$.
I currently have a solution but it is not linear. To explain the solution, consider first the simpler problems 2SUMx1 and 2SUMx2, in which we only look for two numbers $a+b=0$ in either one array or two different arrays. Given an oracle for 2SUMx2, the problem 2SUMx1 can be solved in the following way.
Let $n$ be the number of elements in the input array $S$.
For i = 1 to log(n): Partition the array S to two arrays, X and Y, based on bit i of the index. I.e.: X contains all elements S[k] where bit i of k is 0; Y contains all elements S[k] where bit i of k is 1. Run 2SUMx2(X,Y) If there is a solution, return it and exit. If no solution were found for any i, return "no solution".
This algorithm works because, if there are two different items, $a,b\in S$, whose sum is 0, then their index must have at least one bit different, say bit $i$. So, in iteration $i$ they will be in different parts and will be found by 2SUMx2($X$,$Y$). The time complexity is $O(n \log n)$.
This algorithm can be generalized to 3SUM by using trits instead of bits, and checking all possible pairs of them. The time complexity is therefore $O(n \log^2 n)$.
Is there a linear-time algorithm?