Created
September 29, 2018 22:31
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
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