Original problem · C++ solution
Rearrange the pair condition into a[i]-i = a[j]-j.
Rearrange the pair condition into a[i]-i = a[j]-j. Count earlier equal keys while scanning; each valid pair is counted exactly when its later endpoint arrives.
- Time: O(n log n) per case.
- Extra space: O(n).
Keep the state variables named after the quantities in the invariant. Use standard C++17 containers and check the stated integer bounds.
The number of pairs can exceed a 32-bit integer.
State the invariant without looking at the code. Give one input that breaks the most tempting incorrect approach, then add it to the tests.