Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique
If you must write out all of the pairs individually, then the overall problem takes quadratic time because the running time of this last post-processing step is $O(n^2)$.

If you are allowed to represent the output in a different way, then you can simply keep track of distinct pairs and associate them with a counter (see run-length encoding). Thus, you can compute the solution in $O(n)$ time using the following algorithm:


Initialize an auxiliary array (or hash map) $Aux$.
Perform a first linear scan of the input array $Arr$ and use the auxiliary array to keep track of how many times each of the elements appears. For example, $Aux[2]=3$ indicates that $2$ appears $3$ times in $Arr$.
Perform a second linear scan of the input array $Arr$. During the $i$th iteration, $a=Arr[i]$ and you must look for the element $b =a-k$, which appears $c =Aux[b]$ times in $Arr$. If $c \gt 0$, then you will add the pair $(a,b)$ to your solution, associated with the count $c$. Two special cases that must be considered at step 3:


If the pair already exists in your solution, you can simply increment the existing counter by $c$.
If $k=0$, you must add the pair $(a,b)$ only if $c \gt 1$. The counter associated with this pair will not be set to (or incremented by) $c$, but, rather, by $c-x-1$, where $x$ stores how many times we have seen $a$ before.