# 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.

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.

**3SUM**

Does 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.