Special case of subset sum in $O(n)$
The assumptions $A[i] \in \mathbb N$ and $A[i] + A[j] \leq n$ together imply that $0 \leq A[i] \leq n$, and so $-n \leq A[i]-i \leq n$. This suggests maintaining an array $B[-n],\ldots,B[n]$, initialized with zeroes. We go over the elements of $A$ one by one. We put $B[A[i]-i] = i$, and then check whether $B[i-A[i]]$ is non-zero, say equal to $j$. If so, then $i-A[i] = A[j] - j$, and so $A[i] - i + A[j] - j = 0$. (This allows $i = j$; if you want to disallow it, reverse the order of these two steps.)