题目：
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
链接： http://leetcode.com/problems/two-sum-iii-data-structure-design/
题解：
设计two sum，这道题用hashmap很适合，加入是O(1)，查找的话要遍历整个keyset，所以是O(n)。
Time Complexity - O(n) , Space Complexity - O(n)
public class TwoSum {
Map<Integer, Integer> map = new HashMap<>();
public void add(int number) {
if(map.containsKey(number))
map.put(number, map.get(number) + 1);
else
map.put(number, 1);
}
public boolean find(int value) {
for(int i : map.keySet()) {
int res = value - i;
if(map.containsKey(res)) {
if(res == i && map.get(i) >= 2 )
return true;
if(res != i)
return true;
}
}
return false;
}
}
二刷:
使用了与一刷一样的方法，这样看起来比较慢，要改进。
好好研究了一下discuss，发现了几个问题
- 遍历整个map的时候，用entrySet比keySet快
- 可以建一个set保存之前查询过并且找到答案的value
- 使用ArrayList来保存之前加入过的数字，再遍历这个ArrayList比遍历HashMap的keySet和entrySet都要快很多...
Java:
Time Complexity - O(n) , Space Complexity - O(n)
public class TwoSum {
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> valueSet;
public TwoSum() {
map = new HashMap<>();
valueSet = new HashSet<>();
}
// Add the number to an internal data structure.
public void add(int number) {
if (!map.containsKey(number)) {
map.put(number, 1);
} else {
map.put(number, 2);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
if (valueSet.contains(value)) {
return true;
}
for (int i : map.keySet()) {
int remain = value - i;
if (map.containsKey(remain)) {
if ((remain == i && map.get(remain) > 1) || remain != i) {
valueSet.add(value);
return true;
}
}
}
return false;
}
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);
Reference:
https://leetcode.com/discuss/76823/beats-100%25-java-code