idude idude - 1 year ago 82
Java Question

How to solve this using hashmaps?

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


and you're given that
is the difference between two array elements. How would you find how many times
appears? For example, in this list
appears 3 times

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

Any ideas would be greatly appreciated!

Answer Source

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) {
        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