Can we assume that the difference cannot be negative?! What if k=-2 ? A[0]-A[2]=-2, and hence exists!

k is non negative. My bad! I should change the problem statement to reflect that.

What difference is it going to make if k is allowed to be negative as well?

Yes you can assume that. I tried it and it worked with just a Set