哈希表

常用于快速查找，计数，时间复杂度都是O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//基本操作
unordered_map<string, int> m; // 定义一个哈希表，键为字符串，值为整数
m["apple"] = 1; // 下标访问
if(m.count("apple")){ // 判断 "apple" 是否在哈希表中
    cout << m["apple"] << endl; // 输出 "apple" 对应的值
}
m[c-'a']++; // c为小写字母
// 遍历
for(auto& [key, value] : m){ // C++17 结构化绑定，遍历哈希表
    cout << key << ": " << value << endl; // 输出键值对
}

//将哈希表/集合以vector返回
unordered_set<int> s;
return vector<int>(s.begin(), s.end()); // 将哈希表 s 中的元素以 vector 的形式返回

1. 两数之和

hash表辅助，维护val->下标 找need=target-num的下标 (怎么处理相同元素？)
其实不用，只需要逐位加入哈希表就可以，后面的位自然可以找到前面need的值的索引

202. 快乐数

题中说了会无限循环，那么也就是说求和的过程中，sum会成环，重复出现。当要快速判断一个元素是否出现集合里的时候，就要考虑哈希了。
注意熟练位运算取数

454. 四数相加 II

遍历AB数组，和以及出现次数存入哈希表
遍历CD数组，计算need=target-sum，查询哈希表中need出现的次数，累加到答案里

字符串

1
2
3
4
5
6
7
string s;
// 一段一段处理：在for循环中i加一段

reverse(s.begin(), s.end()); // 反转字符串
// reverse反转的范围是左闭右开区间，reverse(s.begin(), s.end())表示反转整个字符串s。
to_string(num); // 数字转字符串

151. 翻转字符串里的单词

stringstream ss(s);
ss >> word; // 从流中读取单词

实现strstr()匹配

KMP算法

459. 重复的子字符串