博文中会简要介绍Leetcode P0170题目分析及解题思路。
“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.
对于这道题而言，存在两种操作方式，一种是find，另一种是add。一般来说如果这个数据结构插入很多，那么需要尽可能的减少add操作的时间复杂度，而如果寻找加和等于给定target的数对的操作比较多，则需要尽可能控制find的时间复杂度。
通常情况下，有两种解法，一种是利用HashTable的数据结构，使得add操作是O(1)的，并且find操作是O(n)的。还有一种是利用排序，add操作时不排序则是O(1)的，find操作排序则是O(nlogn)的。
虽然看起来第一种好于第二种，但是在第二种方法中我们可以通过记录当前数据结构是否有序来减少排序次数，比如两个find操作之间没有添加操作，那么由于前一次的find操作已经使得数据结构有序了，第二次find的时候就无需再对数据进行排序了。在这种情况下，由于第二种是对有序数组的遍历，可以两头遍历，相对快于对HashTable的所有键的遍历。
以下是Java的题解代码实现。
class TwoSum {
private Map<Integer, Integer> num2CountMap = null;
/** Initialize your data structure here. */
public TwoSum() {
this.num2CountMap = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
this.num2CountMap.put(number, this.num2CountMap.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 (Map.Entry<Integer, Integer> entry: this.num2CountMap.entrySet()) {
int complement = value - entry.getKey();
if (complement != entry.getKey()) {
if (this.num2CountMap.containsKey(complement))
return true;
}
else {
if (entry.getValue() > 1)
return true;
}
}
return false;
}
}
以下是C++的题解代码实现。
class TwoSum {
public:
/** Initialize your data structure here. */
TwoSum() {
}
/** Add the number to an internal data structure.. */
void add(int number) {
++this->num2count[number];
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
for (auto entry: this->num2count) {
int complement = value - entry.first;
if (complement != entry.first) {
if (this->num2count.count(complement) > 0)
return true;
}
else {
if (entry.second > 1)
return true;
}
}
return false;
}
private:
unordered_map<int,int> num2count;
};