这个题考察自己创建一个哈希表。这个题我们用拉链法 O(1)时间复杂度 哈希表的基本思想都是先开一个大数组，然后用某种哈希函数将key映射到数组的下标空间。 不同算法的区别在于如何处理下标冲突，即当两个不同的key被映射到同一下标时，该怎么办。
一般有两种方式处理冲突：拉链法和开放寻址法。 首先我们来介绍拉链法。它的思想很简单，在哈希表中的每个位置上，用一个链表来存储所有映射到该位置的元素。
对于put(key, value)操作，我们先求出key的哈希值，然后遍历该位置上的链表，如果链表中包含key，则更新其对应的value；如果链表中不包含key，则直接将（key，value）插入该链表中。 对于get(key)操作，求出key对应的哈希值后，遍历该位置上的链表，如果key在链表中，则返回其对应的value，否则返回-1。 对于remove(key)，求出key的哈希值后，遍历该位置上的链表，如果key在链表中，则将其删除。 时间复杂度分析：最坏情况下，所有key的哈希值都相同，且key互不相同，则所有操作的时间复杂度都是 O(n)。但最坏情况很难达到，每个操作的期望时间复杂度是 O(1)。 空间复杂度分析：一般情况下，初始的大数组开到总数据量的两到三倍大小即可，且所有链表的总长度是 O(n) 级别的，所以总空间复杂度是 O(n)。
class MyHashMap {
public:
/** Initialize your data structure here. */
const int N = 20011;
vector<list<pair<int, int>>> h;
MyHashMap() {
h = vector<list<pair<int, int>>>(N);
}
list<pair<int, int>>::iterator find(int key){
int t = key % N;
for(auto it = h[t].begin(); it != h[t].end(); it++){
if(it->first == key) return it;
}
return h[t].end();
}
/** value will always be non-negative. */
void put(int key, int value) {
auto it = find(key);
int t = key % N;
if(it == h[t].end()) h[t].push_back({key, value});
else it->second = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto it = find(key);
int t = key % N;
if(it != h[t].end()) return it->second;
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto it = find(key);
int t = key % N;
if(it != h[t].end()) h[t].erase(it);
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
(前缀和，哈希表) O(n) 对原数组求前缀和后，一个和为 k 的子数组即为一对前缀和的差值为 k 的位置。 遍历前缀和数组，用 unordered_map 哈希表记录每个前缀和出现的次数。特别地，初始时前缀和为 0 需要被额外记录一次。 遍历过程中，对于当前前缀和 tot，累计之前 tot - k 前缀和出现的次数累积到答案即可。 时间复杂度 每个位置仅遍历一次，哈希表单次操作的时间复杂度为 O(1)，故总时间复杂度为 O(n)。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
int res = 0;
hash[0] = 1;
//S[L, R] = S[R] - S[L-1],如果L=0，那么就要求S[-1]，所以0出现的次数就为1
for(int i = 0, sum = 0; i < nums.size(); i++){
sum += nums[i];
res += hash[sum - k];
hash[sum]++;
}
return res;
}
};
(并查集) O(n2) 此题为并查集的入门题。 基础的并查集能解决的一类问题是不断将两个元素所在集合合并，并随时询问两个元素是否在同一集合。 定义数组 f(i) 表示 i 元素所在集合的根结点（代表元素）。初始时，所有元素所在集合的根结点就是自身。 合并时，直接将两个集合的根结点合并，即修改 f 数组。 查询时，不断通过判断 i 是否等于 f(i) 的操作，若不相等则递归判断 f(f(i))，直到 i == f(i) 为止。 但以上做法会在一条链的情况下单次查询的时间复杂度退化至线性，故可以采用路径压缩优化，将复杂度降到近似常数。读者可以自行查阅相关资料。 对于此题，最后只需检查有多少个元素为一个集合的根结点即可。 时间复杂度 并查集单次操作的复杂度近似于常数，故总时间复杂度为遍历整个朋友关系数组的复杂度，即 O(n2)。
class Solution {
public:
vector<int> p;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int findCircleNum(vector<vector<int>>& M) {
int n = M.size();
for(int i = 0; i < n; i++){
p.push_back(i);
}
int res = n;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(M[i][j] == 1){
if(find(i) != find(j)){
p[find(i)] = find(j);
res--;
}
}
}
}
return res;
}
};
出现环的条件是某条边，边的两个端点原本就是连通的，那么加上了这条边以后就产生了环，因此我们在加入每条边的时候需要判断一下边的两个端点本身是不是连通的即可。
时间复杂度分析：需要遍历一遍输入的边，对每条边的两个端点进行一下合并操作，合并的复杂度是常数的，所以最后复杂度为O(n)。
class Solution {
public:
vector<int> p;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
for(int i = 0; i <= n; i++) p.push_back(i);
for(int i = 0; i < n; i++){
int first = edges[i][0], second = edges[i][1];
if(find(first) != find(second)){
p[find(first)] = find(second);
}
else return {first, second};
}
return {-1, -1};
}
};
求一个数组里出现次数是前k个的元素。
先把数组的元素加入哈希表，key为元素，value为该元素出现的次数，然后再把该哈希表的key和value插入到一个小根堆里，然后如果小根堆的size大于k，我们就
弹出元素，直到小根堆里面刚好只有k个元素即可。我们这里的pair是个vector，是双排序的，这个题我们希望的是出现次数最多的且字典序最小的输出，那么我们这里
不能直接使用c++的大根堆，只能将value取相反数，这样的话符合pair的排序。
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> hash;
typedef pair<int, string> PIS;
priority_queue<PIS> q;
int n = words.size();
for(int i = 0; i < n; i++) hash[words[i]]++;
for(auto item: hash){
PIS t(-item.second, item.first);
q.push(t);
if(q.size() > k) q.pop();
}
vector<string> res(k);
for(int i = k - 1; i >=0; i--){
res[i] = q.top().second;
q.pop();
}
return res;
}
};
(对顶堆) O(nlogn) 建立一个大根堆，一个小根堆。大根堆存储小于当前中位数，小根堆存储大于等于当前中位数。且小根堆的大小永远都比大根堆大1或相等。 根据上述定义，我们每次可以通过小根堆的堆顶或者两个堆的堆顶元素的平均数求出中位数。 维护时，如果新加入的元素大于等于当前的中位数，则加入小根堆；否则加入大根堆。然后如果发现两个堆的大小关系不满足上述要求，则可以通过弹出一个堆的元素放到另一个堆中。
每次维护堆的时间为O(logn)，取出中位数的时间为O(1)。故总时间复杂度为O(nlogn)。
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int, vector<int>, greater<int>> smaller;
priority_queue<int> larger;
MedianFinder() {
}
void addNum(int num) {
// 这个地方一定是larger.size() == 0，因为如果下面的堆为空的话就往上面的堆插。
if(larger.size() == 0 || num >= larger.top()) smaller.push(num);
else{
larger.push(num);
smaller.push(larger.top());
larger.pop();
}
if(smaller.size() > larger.size() + 1){
larger.push(smaller.top());
smaller.pop();
}
}
double findMedian() {
if((smaller.size() == larger.size())){
return (smaller.top() + larger.top()) / 2.0;
}
else return smaller.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/