LeetCode 170: Two Sum III - Data structure design
Problem Description
Explanation:
To design a data structure that supports two operations:
add(num): Add the numbernumto the data structure.find(target): Find if there exist two numbers such that their sum is equal totarget.
We can use a hashmap to store the numbers and their frequencies. When adding a number, we store it in the hashmap along with its frequency. When finding a pair that sums up to the target, we iterate through the hashmap and check if target - num exists in the hashmap.
Solutions
import java.util.HashMap;
class TwoSum {
private HashMap<Integer, Integer> map;
public TwoSum() {
map = new HashMap<>();
}
public void add(int num) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
public boolean find(int target) {
for (int num : map.keySet()) {
int complement = target - num;
if ((num == complement && map.get(num) > 1) || (num != complement && map.containsKey(complement))) {
return true;
}
}
return false;
}
}Related LeetCode Problems
Loading editor...