In a sorted array, put one pointer at each end. If their sum is too small, the left value is too small for any partner, so move left inward; if too big, move right inward. Each step rules out one value, so it finishes in at most n − 1 steps instead of checking all n² pairs.
- Average time
- O(n)
- Space
- O(1)