# 170. Two Sum III - Data structure design 两数之和 III - 数据结构设计

@TOC

## # 题目描述

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.

Example 1:

``````add(1); add(3); add(5);
find(4) -> true
find(7) -> false
``````

Example 2:

``````add(3); add(1); add(2);
find(3) -> true
find(6) -> false
``````

## # 解题方法

### # 数组+字典

C++代码如下：

``````class TwoSum {
public:
/** Initialize your data structure here. */
TwoSum() {
}

/** Add the number to an internal data structure.. */
nums.push_back(number);
m[number] = nums.size() - 1;
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
for (int i = 0; i < nums.size(); ++i) {
int left = nums[i];
int right = value - left;
if (m.count(right) && m[right] != i)
return true;
}
return false;
}
private:
map<int, int> m;
vector<int> nums;
};

/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();
* bool param_2 = obj->find(value);
*/
``````

### # 平衡查找树+双指针

C++代码如下：

``````class TwoSum {
public:
/** Initialize your data structure here. */
TwoSum() {
}

/** Add the number to an internal data structure.. */
m[number] ++;
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
if (m.empty()) return false;
auto left = m.begin();
auto right = m.end();
right --;
while (left != right) {
int cur_sum = left->first + right->first;
if (cur_sum == value
&& (left != right || left->second > 1))
return true;
else if (cur_sum > value)
right --;
else
left ++;
}
return left->first + right->first == value && (left != right || left->second > 1);
}
private:
map<int, int> m;
};

/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();