170. Two Sum III - Data structure design
設計一個數據結構，它接受一個整數流並檢查是否有一對整數的和等於特定值。
實現 TwoSum 類：TwoSum() 初始化 TwoSum 對象，初始為一個空數組。
void add(int number) 向數據結構添加數字。
boolean find(int value) 返回是否存在任意一對數字，其和等於 value，如果存在返回 true，否則返回 false。
範例 ：
輸入：["TwoSum", "add", "add", "add", "find", "find"] [[], [1], [3], [5], [4], [7]]
輸出：[null, null, null, null, true, false]
解釋：
TwoSum twoSum = new TwoSum(); twoSum.add(1); // [] --> [1] twoSum.add(3); // [1] --> [1, 3] twoSum.add(5); // [1, 3] --> [1, 3, 5] twoSum.find(4); // 1 + 3 = 4, 返回 true twoSum.find(7); // 沒有兩個整數和為 7，返回 false
約束條件：number 的範圍是 -10^5 到 10^5。
value 的範圍是 -2^31 到 2^31 - 1。
最多會進行 10^4 次 add 和 find 調用。
Python
class TwoSum:
def __init__(self):
# Initialize an empty list to store the numbers
self.nums = []
def add(self, number: int) -> None:
# Add the number to the list
self.nums.append(number)
def find(self, value: int) -> bool:
# Use a set to store the numbers we have seen so far
num_set = set()
# Check if there exists any pair of numbers that add up to the given value
for num in self.nums:
if value - num in num_set:
return True
num_set.add(num)
return False
20.87MB, 843ms
C++
#include <unordered_map>
class TwoSum {
private:
std::unordered_map<long long, int> num_count;
public:
TwoSum() {}
void add(int number) {
num_count[number]++;
}
bool find(int value) {
for (const auto& pair : num_count) {
long long complement = static_cast<long long>(value) - pair.first;
if (num_count.count(complement)) {
if (complement != pair.first || pair.second > 1) {
return true;
}
}
}
return false;
}
};
31.74MB, 99ms
Javascript
var TwoSum = function() {
this.numMap = new Map();
};
/**
* @param {number} number
* @return {void}
*/
TwoSum.prototype.add = function(number) {
this.numMap.set(number, (this.numMap.get(number) || 0) + 1);
};
/**
* @param {number} value
* @return {boolean}
*/
TwoSum.prototype.find = function(value) {
for (let [num, count] of this.numMap) {
let complement = value - num;
if (this.numMap.has(complement)) {
if (complement !== num || count > 1) {
return true;
}
}
}
return false;
};
63.91MB, 182ms
