LC170. Two Sum III - Data structure design
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.
这题是easy的，不过有一个挺好玩的地方所以也留个档。
首先是hashmap简单解法：
public class TwoSum {
HashMap<Integer, Integer> map = new HashMap<>();
// Add the number to an internal data structure.
public void add(int number) {
if(map.containsKey(number)) map.put(number, map.get(number) + 1);
else map.put(number, 1);
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for(int key: map.keySet()){
if(map.containsKey(value - key) && value - key != key) return true;
if(value - key == key && map.get(value - key) > 1) return true;
}
return false;
}
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);
O(n), 487ms.
ArrayList优化解法：
public class TwoSum {
List<Integer> list = new ArrayList<Integer>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// Add the number to an internal data structure.
public void add(int number) {
list.add(number);
if (map.containsKey(number))
map.put(number, map.get(number)+1);
else
map.put(number, 1);
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (int i = 0; i < list.size(); i++) {
int num1 = list.get(i);
int num2 = value - num1;
if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2)))
return true;
}
return false;
}
}
O(n), 117ms.
嗯。为什么呢？
The difference is the pattern to access memory. Using
list, you access memory linearly. Basically, theentrySetis an iterator, you can’t guarantee to access memory linearly, so the CPU cache doesn’t work well.
╮(╯▽╰)╭