- Two Sum III - Data structure design 难度 简单
https://leetcode-cn.com/problems/two-sum-iii-data-structure-design/
Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum() Initializes the TwoSum object, with an empty array initially.
void add(int number) Adds number to the data structure.
boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
Example 1:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
Explanation
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, return true
twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-105 <= number <= 105
-231 <= value <= 231 - 1
At most 104 calls will be made to add and find.
相关企业
领英 LinkedIn|2
相关标签
Design
Array
Hash Table
Two Pointers
Data Stream
相似题目
Two Sum 简单
Unique Word Abbreviation 中等
Two Sum IV - Input is a BST 简单
- Add(): just add O(1)
- Find(): sort O(nlogn) and 2 pointers O(n) = O(nlogn)
class TwoSum:
def __init__(self):
self.nums = []
# just add, O(1)
def add(self, number: int) -> None:
self.nums.append(number)
# sort O(nlogn) and 2 pointers find O(n) = O(nlogn)
def find(self, value: int) -> bool:
if len(self.nums) == 0:
return False
self.nums = sorted(self.nums)
left, right = 0, len(self.nums)-1
while left < right:
if self.nums[left] + self.nums[right] == value:
return True
elif self.nums[left] + self.nums[right] < value:
left += 1
elif self.nums[left] + self.nums[right] > value:
right -= 1
return False
# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)- Add(): add and keep sorted O(n)
- Find(): 2 pointers O(n)
class TwoSum:
def __init__(self):
self.nums = []
# add and keep sorted, O(n)
def add(self, number: int) -> None:
self.nums.append(number)
# insert sort (add at end then move left)
index = len(self.nums) - 1
while index > 0 and self.nums[index] < self.nums[index-1]:
self.nums[index], self.nums[index-1] = self.nums[index-1], self.nums[index]
index -= 1
# 2 pointers find, O(n)
def find(self, value: int) -> bool:
if len(self.nums) == 0:
return False
left, right = 0, len(self.nums)-1
while left < right:
twosum = self.nums[left] + self.nums[right]
if twosum == value:
return True
elif twosum < value:
left += 1
elif twosum > value:
right -= 1
return False
# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)class TwoSum {
private List<Integer> nums;
public TwoSum() {
this.nums = new ArrayList<Integer>();
}
public void add(int number) {
this.nums.add(number);
int index = this.nums.size()-1;
while (index > 0 && this.nums.get(index-1) > this.nums.get(index) ){
int temp = this.nums.get(index-1);
this.nums.set(index-1, this.nums.get(index));
this.nums.set(index, temp);
index --;
}
}
public boolean find(int value) {
if (this.nums.size() <= 0){
return false;
}
int left = 0, right = this.nums.size()-1;
while (left < right){
int twosum = this.nums.get(left) + this.nums.get(right);
if (twosum == value) {
return true;
}else if (twosum < value){
left ++;
}else if (twosum > value){
right --;
}
}
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);
*/type TwoSum struct {
nums []int
size int
}
func Constructor() TwoSum {
ts := new(TwoSum)
ts.nums = []int{}
ts.size = 0
return *ts
}
func (this *TwoSum) Add(number int) {
this.nums = append(this.nums, number)
this.size ++
index := this.size - 1
for index > 0 && this.nums[index - 1] > this.nums[index]{
this.nums[index - 1], this.nums[index] = this.nums[index], this.nums[index - 1]
index --
}
}
func (this *TwoSum) Find(value int) bool {
if this.size <= 0 { return false}
left, right := 0, this.size - 1
for left < right {
twosum := this.nums[left] + this.nums[right]
if twosum == value {
return true
}else if twosum < value {
left ++
}else if twosum > value {
right --
}
}
return false
}
/**
* Your TwoSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* param_2 := obj.Find(value);
*/class TwoSum {
private:
vector<int> nums;
public:
TwoSum() {
}
void add(int number) {
this->nums.push_back(number);
int index = this->nums.size() - 1;
while (index > 0 && this->nums.at(index - 1) > this->nums.at(index) ){
std::swap(this->nums.at(index - 1), this->nums.at(index) );
index --;
}
// for (int i =0; i < this->nums.size();i++){
// cout << this->nums[i];
// }
// cout << endl;
}
bool find(int value) {
if (this->nums.size() <= 0 ) { return false;}
int left = 0, right = this->nums.size()-1;
while (left < right){
int twosum = this->nums[left] + this->nums[right];
if (twosum == value){
return true;
}else if (twosum < value){
left ++;
}else if (twosum > value){
right --;
}
}
return false;
}
};
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();
* obj->add(number);
* bool param_2 = obj->find(value);
*/- Add(): O(1) //Elements are unordered.
- Find(): O(n)
class TwoSum:
def __init__(self):
self.nums_ctr = {}
# Hashtable O(1)
def add(self, number: int) -> None:
if number in self.nums_ctr:
self.nums_ctr[number] += 1
else:
self.nums_ctr[number] = 1
# O(n)
def find(self, value: int) -> bool:
if len(self.nums_ctr) == 0:
return False
for num in self.nums_ctr: #this "for" is unordered
if value - num in self.nums_ctr and (value - num != num or self.nums_ctr[num] > 1): # corner case [o, o] with twosum 0
return True
return False
# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)class TwoSum {
private Map<Integer, Integer> nums_ctr;
public TwoSum() {
this.nums_ctr = new HashMap<Integer, Integer>();
}
public void add(int number) {
// if (this.nums_ctr.containsKey(number)) {
// this.nums_ctr.put(number, this.nums_ctr.get(number)+1);
// } else {
// this.nums_ctr.put(number, 1);
// }
// above and below are equivalent
this.nums_ctr.put(number, this.nums_ctr.getOrDefault(number, 0) + 1);
}
public boolean find(int value) {
if (this.nums_ctr.size() <= 0){
return false;
}
for (int num: this.nums_ctr.keySet()){
if (this.nums_ctr.containsKey(value - num) && (value - num != num || this.nums_ctr.getOrDefault(num, 0) > 1) ){
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);
*/type TwoSum struct {
nums map[int]int
size int
}
func Constructor() TwoSum {
ts := new(TwoSum)
ts.nums = make(map[int]int)
ts.size = 0
return *ts
}
func (this *TwoSum) Add(number int) {
this.nums[number] ++
this.size ++
}
func (this *TwoSum) Find(value int) bool {
if this.size <= 0 { return false}
for key, val := range this.nums{
_, exist := this.nums[value - key]
if exist && (value - key != key || val > 1){
return true
}
}
return false
}
/**
* Your TwoSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* param_2 := obj.Find(value);
*/class TwoSum {
private:
unordered_map<long, int> nums;
public:
TwoSum() {
}
void add(int number) {
this->nums[number] ++;
// for (auto x : this->nums)
// cout << x.first << " " << x.second << ", ";
// cout << endl;
}
bool find(int value) {
if (this->nums.size() <= 0 ) { return false;}
for (auto elem : this->nums){
long counterpart = (long)value - elem.first;
if (this->nums.count(counterpart) && (counterpart != elem.first || elem.second > 1)){
return true;
}
}
return false;
}
};
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();
* obj->add(number);
* bool param_2 = obj->find(value);
*/