Find all pairs in an array that sum to a given number without using
HashMap
. Duplicate pairs are not allowed. Input array cannot be modified.input:
{-2, -1, -1, 5, 7, 7, 7, 7, 8}
, target =7
output:
(-1, 8)
As it is mentioned, using HashMap
is not allowed, so I decided to use binary search.
public class TwoSumProblemUsingBinarySearch {
public static class Pair {
private final int x;
private final int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public boolean equals(Object other) {
if (other instanceof Pair) {
Pair o = (Pair) other;
return this.x == o.x && this.y == o.y;
}
return false;
}
@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}
}
public static Set<Pair> findAllParis(int input[], int target) {
int numbers[] = Arrays.copyOf(input, input.length);
Set<Pair> pairs = new HashSet<>();
Arrays.sort(numbers);
for (int low = 0, high = input.length - 1; low < high; ) {
int sum = input[low] + input[high];
if (sum > target) {
high--;
} else if (sum < target) {
low++;
} else {
pairs.add(new Pair(input[low], input[high]));
high--;
low++;
}
}
return pairs;
}
}
@Test
public void findAllParis() throws Exception {
System.out.println(TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7));
assertEquals(1, TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7).size());
}