Then 3-SUM can be solved in O(n) memory and O(n^2) time, by storing all h_i
as keys in a set S, and running
for i = 1 to n
for j =i+1 to n
if S contains -(h_i + h_j) mod d
then 3-SUM found
You've got another problem here in that it is trivial to trade-off memory for time
(e.g. do the above twice, first for half of S that is even, then for the other half that's odd).
So 2-SUM and 3-SUM both seem to be memory-easy rather than memory-hard.
4-SUM and higher don't seem immune to such trade-offs either.