一、题目
提示：
0 <= key <= 10^6
最多调用 104 次 add、remove 和 contains
二、思路
哈希表有个2个关键问题：
哈希函数：将任意值通过哈希函数映射到固定值，可以设哈希表的大小为b a s e basebase，输入哈希函数值为k e y keykey，设计一个简单的哈希函数：h a s h ( k e y ) = k e y m o d b a s e hash(key) = key \quad mod \quad basehash(key)=keymodbase。其中b a s e basebase一般取为质数，可以取987。
哈希表一般使用链地址法，即让每个vector元素是一个链表list。对哈希表的增删改查都是通过hash函数计算后，对这个list进行增删改查即可。
PS：
对vector<list<int>>a进行初始化大小时，如果是直接用vector<list<int>>a(987);是会报错的，可以定义后再用a.resize(987)，但是这样是产生对象后才扩容到987，效率更快的写法是：MyHashSet():a(987){}，即在构造a时就是987大小了。
在C++的STL中，map或者set可以直接使用find，但是vector或者list是不可以直接使用find的。
三、代码
class MyHashSet { private: vector<list<int>>a; int base = 987; int hash(int key){ return key % base; } public: MyHashSet(){ a.resize(987); } void add(int key) { int temp = hash(key); for(auto it = a[temp].begin(); it != a[temp].end(); it++){ if(*it == key){ return; } } a[temp].push_back(key); } void remove(int key) { int temp = hash(key); for(auto it = a[temp].begin(); it != a[temp].end(); it++){ if(*it == key){ //注意这里不能写成erase(key) a[temp].erase(it); return; } } } bool contains(int key) { int temp = hash(key); for(auto it = a[temp].begin(); it != a[temp].end(); it++){ if(*it == key){ return true; } } return false; } }; /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet* obj = new MyHashSet(); * obj->add(key); * obj->remove(key); * bool param_3 = obj->contains(key); */
