idude - 1 year ago 82
Java Question

# How to solve this using hashmaps?

Suppose you're given a list of the following values:

``````[1,4,5,7,8,9]
``````

and you're given that
`k=4`
where
`k`
is the difference between two array elements. How would you find how many times
`k`
appears? For example, in this list
`k`
appears 3 times
`[(5-1),(8-4),(9-5)]`

I was able to solve this using two for loops but that requires
`O(n^2)`
time. I heard this could be solved using hashmaps, but am unsure how to would implement it?

Any ideas would be greatly appreciated!

The idea to is to store all the possible differences between the k and each value in the input array (`numbers`). Then count the number of values in the input array that fits the difference.

This will work:

``````public class Solution {
public int twoSum(int[] numbers, int k) {
if (numbers == null) {
return null;
}
int count = 0;
HashMap<Integer, Integer> difference = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
difference.put(k - numbers[i], i);
}
for (int i = 0; i < numbers.length; i++) {
int cur = -numbers[i];
if (difference.containsKey(cur) && difference.get(cur) != i) {
count++;
}
}
return count;
}
}
``````

The catch is to have `difference.get(cur) != i` condition in place (where `i` is the index `cur`) to avoid the case of having `k = 0` and each value would form a pair with itself.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download