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
Idea 1. Similar to Two Sum LT1, if numbers are unique, set would be enough, otherwise map to store frequency for each number. 遍历hashmap, 对于每个数num，找target - num,
record[num] >= 2 if target - num = num
record[target - num] >= 1 if target - num != num
Time complexity: O(1) for add, O(n) for find, or alternatively add set to store the sum, so that O(n) for add, O(1) for find
Space complexity: O(n)
public class TwoSum {
private Map<Integer, Integer> record = new HashMap<>();
public void add(int number) {
record.put(number, record.getOrDefault(number, 0) + 1);
}
public boolean find(int value) {
for(int key: record.keySet()) {
int another = value - key;
if(key == another) {
if(record.get(another) >= 2) {
return true;
}
}
else {
if(record.containsKey(another)){
return true;
}
}
}
return false;
}
public static void main(String[] args) {
TwoSum subject = new TwoSum();
subject.add(1);
subject.add(3);
subject.add(4);
System.out.println(subject.find(4));
System.out.println(subject.find(7));
}
}
slightly more conciser:
public class TwoSum {
private Map<Integer, Integer> record = new HashMap<>();
public void add(int number) {
record.put(number, record.getOrDefault(number, 0) + 1);
}
public boolean find(int value) {
for(int key: record.keySet()) {
int another = value - key;
if((key == another && record.get(another) >= 2)
|| (key != another && record.containsKey(another))){
return true;
}
}
return false;
}
}