【LeetCode.170】Two Sum III - Data structure design（C++）

问题描述

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.

示例

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

counter用哈希

class TwoSum { 
public:
    void add(int number) { 
        ++m[number];//第一次出现的key的value为0，再++
    }
    bool find(int value) { 
        for (auto a : m) { 
            int t = value - a.first;
            if ((t != a.first && m.count(t)) || (t == a.first && a.second > 1)) { 
                return true;
            }
        }
        return false;
    }
private:
    unordered_map<int, int> m;
};

++m[number]这句很方便，实际上你可以当单独这么用m[key];，这样map里面只有一个key，其value为int的默认值0。
m.count(t)返回map中t这个key出现的次数，由于unordered_map不支持重复的key，所以当t的key存在时就返回1，否则返回0。
(t != a.first && m.count(t))，差值t不与a.first相同，那么t必须存在与key中；(t == a.first && a.second > 1)，差值t与a.first相同，那么t必须出现两次或者说a.second必须大于1。

unordered_map m;
```
m[1];
if (m[2] == 0)
    cout << "fsdf";
```