Algorithms - find x+y = Z in AVERAGE CASE O(n)

So here is the exact question:

Given a set S of n integers and another integer Z, determine whether or not there exist two elements x, y in S whose sum is exactly Z. Give an algorithm for this problem that runs in O(n) average-case time.

Im rather confused on how to approach this problem, because of the average case limitation. Solving it in O(n^2) is simple, but i feel like a different method entirely is needed to solve this...

My first inclination was something involving counting sort or a randomized partition sort (because that is what we have recently been covering in class). Can anyone point me in the right direction/explain this problem to me?

Edit: I now know im supposed to use a data structure we've recently gone over, either a hash table or a binary search tree. Still the average case complexity is getting me... any help?

Thanks for the help in advance!