Actually, there is a method to solve this problem in O(3/2 * n) Assume the maximum value is m, minimum value is n 1. hash these value into a table, with size m - n + 1, cost O(n), assume this table is noted as H 2. {(x, y) | x + y = z} must be reside in H followed by this condition:
{(x, y) | x = H(i), y = H(m - n - i), x, y are not empty, i = z - n + 1}, this will cost O(1/2 * n)