CareerCup

public static int getDiffPair(int a[] , int diff){
		HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

		int count = 1;
		for(int i = 0;i<a.length;i++){
			if(hashMap.containsKey(a[i])){
				count = hashMap.get(a[i]);
				hashMap.put(a[i], ++count);
			}else{
				hashMap.put(a[i], 1);
			}
		}
		count = 0;
		for(int j = 0;j<a.length;j++){
			if(hashMap.containsKey(a[j]+diff)){
				count+=hashMap.get(a[j]+diff);
			}
		}
		return count;
	}

First of all, what I would do, was to use a

HashMap<Integer, LinkedList<Integer>> hashMap;

So that I could also store the location of other index. If you just need the count, then use hashMap.get(i).size(). This way you can also identify the pairs, as well as the number of repetitions.

However, the array in your example is sorted. In such a case, you can actually solve it in O(1) space and O(N + M) time where "N" is the length of input, and "M" is the number of pairs of indices with a difference equal to "K". I used the idea from a O(1) space solution for 3-sum problem (google it).

Keep two pointers pos_1 <= pos_2. If array is sorted ascendingly, then array[pos_2] >= array[pos_1].

1- Check cmp = array[pos_2] - array[pos_1].
2- If "cmp" is smaller than "k", the desired difference, increase pos_2 to obtain a larger difference. Else, decrease pos_1.
3- If cmp == 0, then you already found a pair [pos_1, pos_2]. All you need to do is to resolve the repeated element case. For that, increase pos_1 until the value changes. Do the same for pos_2. Then generate all the possible tuples (pos_1, pos_2) for the ranges you found.

Here is the java code.

public static void main(String[] args) {
        int[] arr = {1, 1, 5, 5, 5, 6, 9, 16, 27};
        listKdiff(arr, 4);
    }

public static void listKdiff(int[] arr, int k) {
   int pos_1 = 0;
   int pos_2 = 0;
   while(pos_2 < arr.length) {
      int cmp = arr[pos_2] - arr[pos_1];
      if (cmp < k) {
         pos_2++;
      }
      else if (cmp > k) {
         pos_1++;
      }
      else {
// length of the subarrays of equal values starting from    pos_1 and pos_2

         int len1 = 0, len2 = 0; 
         while (arr[pos_1 + len1] == arr[pos_1]) {
            len1++;                                    
         }
         while (arr[pos_2 + len2] == arr[pos_2]) {
            len2++;
               if (len2 + pos_2 == arr.length - 1) {
                  break;
               }
            }
            // print all pairs of duplicates
            for (int i = 0; i < len1; i++) {
               int a = pos_1 + i;
               for (int j = 0; j < len2; j++) {
                  int b = pos_2 + j;
                  System.out.println("[" + a + ", " + b + "]");
                }
            }
            pos_1 = pos_1 + len1;
            pos_2 = pos_2 + len2;				                                
         }
      }
}

This is the output I got. The first 6 pairs corresponds to combinations of (1, 5) and the last three are combinations of (5, 9) (I printed the indices):

[0, 2] 
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 6]
[3, 6]
[4, 6]

public static int getDiffPair(int a[] , int diff){
		HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

		int count = 1;
		for(int i = 0;i<a.length;i++){
			if(hashMap.containsKey(a[i])){
				count = hashMap.get(a[i]);
				hashMap.put(a[i], ++count);
			}else{
				hashMap.put(a[i], 1);
			}
		}
		count = 0;
		for(int j = 0;j<a.length;j++){
			if(hashMap.containsKey(a[j]+diff)){
				count+=hashMap.get(a[j]+diff);
                                              hashMap.put(a[i],0);
			}
		}
		return count;
	}

Oh, I figured out how to do it in two passes, but i'm still wondering if you can do it with only one.

public static int arrayPairDifference(int[] a, int k)
    {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int count = 0;
        for (int i = 0; i < a.length; i++)
        {
            hashMap.put(i, a[i]);
        }
        for (int j = 0; j < a.length; j++)
        {
            if (hashMap.containsValue(a[j] + k))
            {
                count++;
            }
        }
        return count;
    }

with duplication, the problem became quiet tricky.
There are couples of solutions for this, it all depends if we can change the original data, if we could use extra space, etc.
1) the safest way(no extra space, and easy to code) is that we use two-layer loop.
for ith element a[i], we check how many k-a[i] in the rest of subarray. No extra space, for small array, it should be the fast way, even it's time complexity is O(n).
2) if we could change the original input array, we could first sort the array(if it's not sorted), for each element a[i], we do binary search on subarray a[i+1]...a[n-1]. we need to do this twice, since we want to find how many k-a[i] in the subarray, we use adapted binary search algorithm to find the lowest index and highest index with the value of k-a[i], the time complexity will be O(nlg(n)), but it's error-prone. For example: a=[2 6 6 6 9], run this on array a.
3) use a extra hashmap, this is very tricky if there are duplicated elements, for example, for array: a=[2 2 2 2] and K=4, the resulting number of pairs should be 6. we could create a map, with the keys be element values, and values are the number of occurrences, when we scan through the array, for element a[i], first we need to decrement the value of hashMap[a[i]] by one, and then count how many k-a[i] there. otherwise, you will get 16 instead of 6 for the input array a=[2,2,2,2] and K=4. the time complexity for this algo is O(n).