An index at each end of an array, moving in. Each move rules out a whole row of candidate pairs, so n − 1 checks do the work of n(n − 1)/2.
This interactive visualization needs JavaScript.