Given an array of integers and a target value K, find the count of pairs of array elements that have a difference equal to the target value, K.
Example:
Given A = { 1, 2, 3, 5, 7 } and Target = 2
Answer: 2 since there are two pairs in this list whose difference equals to 2
Solution:
This problem is very similar to ADD TO TARGET ALGORITHM, just a subtle but very important difference.
The optimal solution that will run O(N) time would be to use the dictionary data structure.
First, we will run through the array elements and throw a(i) - target in to the dictionary because we want to find any element in the array if it is a(i) - target, where a(i) is any element of the array. This makes sense if we solve for b in the equation:
a(i) - b = target. [find any two pairs a(i) , b so that a(i) - b = target]. Therefore, b = a(i) - target
Then we are going to iterate through the array elements second time and find if any one of them are present in the dictionary and if it does then that is what we want.
public int solution(int[] A, int K) {
int count = 0;
HashSet<string> myhash = new HashSet<string>();
for (int i = 0; i < A.Length; i++) {
if(A[i]>K) {
myhash.Add((A[i]-K).ToString());
}
for (int i = 0; i < A.Length; i++) {
if (myhash.Contains(A[i].ToString())) {
count++;
}
}
return count;
}