Two Sum III - Data structure design
8/17/2018 update:
关于重复的问题。如果sum是其中一个数的2倍。下面这种方法存频率是因为已经把所有数都加入hashmap了。如果是边加 边判断则不需要保存频率,直接用hash set可以解决。
Analysis:
The tricky part of this problem is that how to deal with duplicates. Use hashtable to store each number as key and the occurrence of the number as value.
Inside find() method, iterate through the hashtable, find key target - currentValue. If the key to find is equivalent to current value, make sure the current value exists more than twice or we get wrong answer.
add() is O(1) , find is O(n), space is O(n).
Solution:
关于重复的问题。如果sum是其中一个数的2倍。下面这种方法存频率是因为已经把所有数都加入hashmap了。如果是边加 边判断则不需要保存频率,直接用hash set可以解决。
Analysis:
The tricky part of this problem is that how to deal with duplicates. Use hashtable to store each number as key and the occurrence of the number as value.
Inside find() method, iterate through the hashtable, find key target - currentValue. If the key to find is equivalent to current value, make sure the current value exists more than twice or we get wrong answer.
add() is O(1) , find is O(n), space is O(n).
Solution:
class TwoSum {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
/** Initialize your data structure here. */
public TwoSum() {
}
/** Add the number to an internal data structure.. */
public void add(int number) {
int count = map.containsKey(number) ? map.get(number) : 0;
map.put(number, ++count);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
int num = entry.getKey();
int y = value - num;
if (y == num) {
if(map.get(num) >= 2) return true;
} else {
if(map.containsKey(y)) return true;
}
}
return false;
}
}
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* obj.add(number);
* boolean param_2 = obj.find(value);
*/
评论
发表评论