Problem: find (i,j), i<j, s.t. a[i] + a[j] = i + j
I propose the following approach:

Set
b[i] = a[i]  i
The problem becomes:find (i,j), i<j, s.t. b[i] + b[j] = 0
Complexity: O(n) 
Create objects
c[i] = (b[i],i)
, a struct for example, in a std::vector (or std::array)
Complexity: O(n) 
Sort the
c[i]
pairs according tob
values > getd[j] = (v[j], i[j])
, sorted array
Complexity: O(nlogn) 
Find all pairs
j,k
such thatv[j] = v[k]
Complexity: the array being sorted, should be O(n) 
keep the cases
i[j] < i[k]
Complexity: O(n)