The 3SUMx3 problem can be reduced to the following set intersection problem:

Given two collections of sets, S and T, find a set from collection S that intersects a set from collection T.

The reduction uses an almost linear hash function.

The hash function maps every element in the three input arrays, X Y and Z, to the range {0,...,R-1}, where R is a certain constant.

Create a collection S based on the elements of X in the following way:

For every ${\displaystyle j=0,...,{\sqrt {R}}-1}$:

${\displaystyle S_{j}={h(x_{1})-j,...,h(x_{n})-j}}$

Create a collection T based on the elements of Y in the following way:

For every ${\displaystyle k=0,...,{\sqrt {R}}-1}$:

${\displaystyle T_{k}={-h(y_{1})+k{\sqrt {R}},...,-h(y_{n})+k{\sqrt {R}}}}$

Any element in the intersection of ${\displaystyle S_{j}}$ and ${\displaystyle T_{k}}$ corresponds to an ${\displaystyle x\in X}$ and a ${\displaystyle y\in Y}$ such that:

${\displaystyle h(x)-j=-h(y)+k{\sqrt {R}}}$

${\displaystyle h(x)+h(y)=j+k{\sqrt {R}}}$

The expression ${\displaystyle j+k{\sqrt {R}}}$ is always in the range 0,...,R-1, which is the range of h. If there is a ${\displaystyle z\in Z}$ such that ${\displaystyle h(z)=j+k{\sqrt {R}}}$, then we have:

${\displaystyle h(x)+h(y)=h(z)}$

so we have a candidate for a triple having:

${\displaystyle x+y=z}$

---

The main loop is (given arrays A, B and C):

For every z in array C:

If check(z, A,B)

Return

Where the check function checks if there are elements x∈A and y∈B such that: x+y=z.

The check function can be implemented using 2SUM; this takes time O(n), and since it is activated for every element of C, the total run time is O(n^2). But with a solver for an intersection problem, we can do better.