= Solution
Use two indices, initially the first and last positions of the ordered <sequence>. The two elements occupy distinct positions, so continue only while `i < j`:
``
i := 0; j := n-1;
WHILE i < j DO
t := S[i] + S[j];
IF t = x THEN RETURN TRUE
ELSIF t < x THEN i := i+1
ELSE j := j-1
END
END;
RETURN FALSE
``
The <loop invariant> is: a solution exists in the original input if and only if one exists with both indices in `[i,j]`. If `S[i]+S[j] < x`, then `S[i]+S[k] <= S[i]+S[j] < x` for every `k <= j`, so index `i` cannot belong to a remaining solution. If the sum is too large, `S[k]+S[j] >= S[i]+S[j] > x` for every `k >= i`, so index `j` cannot belong to one. This proves preservation of the <loop invariant>. Equality gives the desired pair, and an interval with fewer than two positions contains none.
Every unsuccessful iteration decreases the <loop variant> `j-i` by one, so there are at most $n-1$ sum comparisons and only <constant space> is needed. Duplicate values are permitted if they occupy distinct positions. Under exact constant-cost real arithmetic and endpoint access,
$$
\boxed{\text{two-pointer two-sum uses }O(n)\text{ time and }O(1)\text{ auxiliary space}.}
$$
Back to article page
