Skip to content

Instantly share code, notes, and snippets.

@KodeSeeker
Created September 29, 2018 22:31
Show Gist options
  • Save KodeSeeker/56639e2dabae50bf97ee37be3995940e to your computer and use it in GitHub Desktop.
Save KodeSeeker/56639e2dabae50bf97ee37be3995940e to your computer and use it in GitHub Desktop.
Design and implement a TwoSum class. It should support the following operations: add and find.
/**
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
**/
import java.util.HashMap;
import java.util.Map;
public class TwoSumDS {
private Map<Integer, Integer> map = new HashMap<>();
public void add(int n) {
if (map.containsKey(n)) {
map.put(n, map.get(n) + 1);
} else {
map.put(n, 1);
}
}
public boolean find(int target) {
// check to see if map has any elements
for (int n : map.keySet()) {
int minus = map.get(target - n);
if (map.containsKey(minus)) {
if (minus == n) // if there are two identical numbers like 2+2 = 4
return map.get(n) > 1; // Is there more than value of n?
return true; // for all other cases where minus =m
}
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment