Let $N,M>n,m$ be integers (to be defined later), and $u,v\in R^N$ be vectros defined as: $$u[i] = \#\{x\in A\colon M-x\equiv i \; (\text{mod }N) \}$$ $$v[i] = \#\{y\in B\colon M+y\equiv i \; (\text{mod }N) \}$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is such $k$ that: $$\forall x\in A\exists y\in B: y-x=k$$ Then we can conclude: $$ w[k\text{ mod } N]=\sum_{i: v[i]\neq 0} v[i] u[(i-k)\text{ mod } N]= n$$ Which by construction, is the maximum value that $w$ can attain. Therefore, we only need check if $\max_i w(i)=n$ or not. Then verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $N \log N$ time, and then finding the maximum element and verifying it takes $n$ steps, so overall $\mathcal{O}(N \log N)$ time and space.
If the numbers in both sets are bounded by $N$ this is an exact solution. But if you pick $N$ too small, $w(i)=n$ can happen only because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$, but there might be several of them, but their number can be bounded. To have $\ell$ such indices, one must have at least $1+2+\dots + \ell$ collisions, which implies: $$P\left(\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell\right) \le P\left(\text{# collisions}\ge \binom{\ell}{2}\right)$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number such that $N>m$, and pick $M$ uniformly at random from $[N]$, the collision probability is bounded by $1/2m$, and by Markov: $$\le \frac{nm/N}{\ell^2/2}\le \frac{n}{\ell^2}$$ So with probability as close to $1$ as you want, $\ell=\mathcal{O}(\sqrt{n})$. Therefore, the overall time complexity of the algorithm is $$\mathcal{O}(n\sqrt{n} + m\log m)$$ in which $m\log m$ is the FFT and iFFT step (since we set $N=2m$), and $n \sqrt{n}$ is the verification step.
There are two ways I see to improve this: 1) One can run the $\log n$ separate instances of the algorithm without the verification, and show that the number of shared collisions would drop by $1/2$ or some other constant every time. 2) One can construct a better hashing mechanism for $u$ and $v$ and use higher moments for Markov and make the concentration sharper.