My code:
public class TwoSum {
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
// Add the number to an internal data structure.
public void add(int number) {
if (tracker.containsKey(number)) {
tracker.put(number, tracker.get(number) + 1);
}
else {
tracker.put(number, 1);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (Integer curr : tracker.keySet()) {
int target = value - curr;
if (tracker.containsKey(target)) {
if (target != curr)
return true;
else {
if (tracker.get(curr) >= 2)
return true;
}
}
}
return false;
}
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);
看的答案。不错。
http://www.programcreek.com/2014/03/two-sum-iii-data-structure-design-java/
Anyway, Good luck, Richardo!
这道题目还是挺有意思的。
虽然我这次没做出来。
最后的AC解法和我的解法其实差不多。说下差距。
- 我为了让逻辑更加清楚，用了更多的嵌套的if else,因此TLE,而AC 的解法，就没有嵌套，更快。
- AC里面更好的解法是把unique的数字插在一个链表里面。重复出现的只用插入一次。这样做有两个好处。
遍历链表的元素个数小于遍历哈希表的。
其次，哈希表遍历的复杂度是 O(n) rather than O(k), k = number of key
而链表的复杂度是O(m), m <= k
所以加入链表后作为一个遍历的机制，更快。
reference:
https://discuss.leetcode.com/topic/32786/beats-100-java-code/8
Anyway, Good luck, Richardo! -- 09/02/2016
