idude - 4 months ago 13

Java Question

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

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

and you're given that

`k=4`

`k`

`k`

`k`

`[(5-1),(8-4),(9-5)]`

I was able to solve this using two for loops but that requires

`O(n^2)`

Any ideas would be greatly appreciated!

Answer

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.