Finding number of number pairs with given difference pairs() is a function which returns the total number of combinations whose difference is k.

     static int pairs(int[] a,int k) {
        int counter=0;
         for (int i : a.length ) {
           for(int j=i+1;j&lt;a.length;j++){
                 if(a[i]-a[j]==k||a[i]-a[j]==-k){
                   counter++;
                 }
                }
           }

 return counter;
}


a is an array of numbers and k is the difference of numbers that are given by user.  I have to find the total number of combinations with a difference of k.  I have done this code, but I want a more optimized code.
Current complexity is \$O(n^2)\$, you can accomplish this with \$O(n \space log \space n)\$ instead by sorting the array first and then loop through the elements.

Let's say that you know that the array is sorted, and the array is for example 4 8 15 16 23 42 and you want to find the diff 7:

Let's initialize two variables, lowIndex, highIndex to both 0.


Now we compare index 0 to index 0, i.e. 4 and 4. It's less than the diff value (7) so we increase highIndex
Compare index 0 to index 1, 4 vs. 8, still less than 7, so highIndex++
Compare index 0 to index 2, 4 vs. 15, that's more than 7, so lowIndex++
Compare index 1 to index 2, 8 vs. 15, that's exactly 7, so we have a match and we do highIndex++
Compare index 1 to index 3, 8 vs. 16, that's more than 7, so lowIndex++
Compare index 2 to index 3, 15 vs. 16, that's less than 7, so highIndex++
Compare index 2 to index 4, 15 vs. 23, that's more than 7, so lowIndex++
Compare index 3 to index 4, 16 vs. 23, that's exactly 7, so we have a match and we do highIndex++
Compare index 3 to index 5, 16 vs. 42, that's more than 7, so lowIndex++
Compare index 4 to index 5, 23 vs. 42, that's more than 7, so lowIndex++
Compare index 5 to index 5, 42 vs. 42, that's less than 7, so highIndex++
highIndex has reached the end of the array, return the number of matches found.