Two Sum III – Data structure design
two sum问题, 这次要写的是一个data structure, 用map计数即可, 注意一下两个数相同的情况.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class TwoSum { Map<Integer, Integer> count; /** Initialize your data structure here. */ public TwoSum() { count = new HashMap<>(); } /** Add the number to an internal data structure.. */ public void add(int number) { count.put(number, count.getOrDefault(number, 0) + 1); } /** Find if there exists any pair of numbers which sum is equal to the value. */ public boolean find(int value) { for(int n : count.keySet()) { int m = value - n; if(n == m && count.get(n) >= 2) return true; else if(n != m && count.get(m) != null) 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); */ |