For this problem, one can assume $M$ to be bigger than $n$, say $M\gg n^a,$ where $a>1,$ and the case $a \in (1,2)$ is of particular interest.

Perhaps the following is easier? Instead of looking for $x+y=z$ for $x,y,z$ in $A,$ look for $x+y+z=0,$ which then is the question 

*Is the set $(A-A) \cap A$ nonempty?*

where now one takes $A \subset \{-M,-M+1,\ldots,M\}$.