Special case of subset sum in $O(n)$ A sorted array $A[1..n]$ is given. Each element of $A[i]\in \mathbb{N}$, and for each $A[i],A[j]$ we have $A[i]+A[j]\leq n$. Find two elements $A[i], A[j]$ such that $(A[i]-i)+(A[j]-j)=0$. Give a deterministic $O(n)$ time algorithm for this problem.
I tackle with this problem as follow :
Calculate each $A[i]-i$ , and insert it into hash table $T$ that take $O(n)$ , then one time traverse $A$ such that to find and element that $A[i]-i=T[i]$. Each search take $O(1)$ in expected, but we must give a deterministic 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.)