# A common **3SUM-hard** reduction

I’m writing this to address a problem I often hear from friends. They usually get it from some technical interview.

Problem1

Let $A$ be an array of $n$ numbers, decide if there exist index $i,j,k$, such that $A[i]+A[j]=A[k]$.

The problem is **3SUM-hard**. We reduce the problem **3SUM** to the above problem in linear time.

Problem2

**3SUM**3SUMDoes there exist $a,b,c\in S$, such that $a+b+c=0$?

Consider a instance of **3SUM**. Let $m=3 \max(S \cup -S)+1$. Store $\{m\}+S$ and $\{2m\}-S$ as elements in the array $A$.

Claim: There exist i,j,k such that $A[i]+A[j]=A[k]$ iff there exist $a,b,c\in S$ such that $a+b+c=0$.

If there exist $i,j,k$ such that $A[i]+A[j]=A[k]$, this implies $A[i]=a+m,A[j]=b+m,A[k]=2m+(-c)$ for some $a,b,c\in S$. The other direction is similar.