Solution of LeetCode Two Sum III – Data structure design using java
add – O(n) runtime, find – O(1) runtime, O(n 2 ) space – Store pair sums in hash table:
We could store all possible pair sums into a hash table. The extra space needed is in the order of O(n2 ). You would also need an extra O(n) space to store the list of added numbers. Each add operation essentially go through the list and form new pair sums that go into the hash table. The find operation involves a single hash table lookup in O(1) runtime.
This method is useful if the number of find operations far exceeds the number of add operations
add – O(log n) runtime, find – O(n) runtime, O(n) space – Binary search + Two pointers:
Maintain a sorted array of numbers. Each add operation would need O(log n) time to insert it at the correct position using a modified binary search . For find operation we could then apply the [Two pointers] approach in O(n) runtime
add – O(1) runtime, find – O(n) runtime, O(n) space – Store input in hash table:
A simpler approach is to store each input into a hash table. To find if a pair sum exists, just iterate through the hash table in O(n) runtime. Make sure you are able to handle duplicates correctly
public class TwoSum {
private Map<Integer, Integer> table = new HashMap<>();
public void add(int input) {
int count = table.containsKey(input) ? table.get(input) : 0;
table.put(input, count + 1);
}
public boolean find(int val) {
for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
int num = entry.getKey();
int y = val - num;
if (y == num) {
// For duplicates, ensure there are at least two individual numbers.
if (entry.getValue() >= 2) return true;
} else if (table.containsKey(y)) {
return true;
}
}
return false;
}
}