Two pointers

On sorted data, 'the sum is too small' means the left pointer can move right with certainty - discarding every pair involving the old left value. n²/2 candidates become n steps.