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.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
class TwoSum
{
private:
map<int,int> fmap;
public:
void add(int x)
{
if(!fmap.count(x))fmap[x]=;
else fmap[x]++;
}
bool find(int target)
{
for (map<int,int>::iterator iter=fmap.begin();iter!=fmap.end();iter++)
{
int i=iter->first;
if(fmap.count(target-i))
{
if(i!=target-i)return true;
else if(fmap[i]>=)return true;
}
}
return false;
}
};