Find all pairs in an array whose absolute difference equals x I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute difference is equal to x.

For example, take A = {13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46} and x = 8, my algorithm should print this:



0 &amp; 3 with values 13 &amp; 21
1 &amp; 5 with values 1 &amp; 9
2 &amp; 4 with values -8 &amp; 0
5 &amp; 7 with values 9 &amp; 17
6 &amp; 10 with values -54 &amp; -46


I worked out a solution, however, it is \$O(n^2)\$:



for (int i = 0 ; i &lt; A.length; i ++)
    {
        for (int j = i; j &lt; A.length; j++)
        {
          if (abs(A[i]-A[j]) == x)
             System.out.println("Indices " + i + " &amp; " + j + " with values " + A[i] + " &amp; "+ A[j]);
        }      
    }



Without sorting first, is there any way to optimize this code to be faster? I know \$O(n^2)\$ isn't great but I can't think of a better way of doing it (without sorting first).
For my algorithm, the best case Omega is also \$Ω(n^2)\$, correct? I need to compare every value in any case.
I don't have the rep to comment, and I know you said without sorting first, but if you are already at worst case performance of O(n^2), and sorting in theory is O(nlogn), why not then sort if it wont hurt your big-o performance? 

i.e.

A.sortAscending() // however done in java. in theory is O(nlogn)

int j = 0;
for (int i = j; i &lt; A.len; i++) {
    while (j &lt; A.len &amp;&amp; (abs(A[i] - A[j++]) &lt; x))
        ; // do nothing

    // so now we are guarenteed absdiff(arr[i], arr[j]) &lt;= x.
    // as soon as it != x we can move on because as the array is sorted
    // the difference will only increase, thus not equaling x again
    while (j &lt; A.len &amp;&amp; (abs(A[i] - A[j++]) == x))
        resultArray.add((arr[i], arr[j])
}