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)

Reply via email to