散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
更加详细的介绍请戳这：
1. 两数之和题目来源于 LeetCode 上第 1 号问题： Two Sum。
题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目解析
使用散列表来解决该问题。
首先设置一个 map 容器 record 用来记录元素的值与索引，然后遍历数组 nums 。
每次遍历时使用临时变量 complement 用来保存目标值与当前值的差值
在此次遍历中查找 record ，查看是否有与 complement 一致的值，如果查找成功则返回查找值的索引值与当前变量的值i
如果未找到，则在 record 保存该元素与索引值 i
动画描述// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> record;
for(int i = 0 ; i < nums.size() ; i ++){
int complement = target - nums[i];
if(record.find(complement) != record.end()){
int res[] = {i, record[complement]};
return vector<int>(res, res + 2);
}
record[nums[i]] = i;
}
}
};
2. 无重复字符的最长子串
题目来源于 LeetCode 上第 3 号问题： Longest Substring Without Repeating Characters 。
题目描述给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
题目解析建立一个 HashMap ，建立每个字符和其最后出现位置之间的映射，然后再定义两个变量 res 和 left ，其中 res 用来记录最长无重复子串的长度，left 指向该无重复子串左边的起始位置的前一个，一开始由于是前一个，所以在初始化时就是 -1。
接下来遍历整个字符串，对于每一个遍历到的字符，如果该字符已经在 HashMap 中存在了，并且如果其映射值大于 left 的话，那么更新 left 为当前映射值，然后映射值更新为当前坐标i，这样保证了left始终为当前边界的前一个位置，然后计算窗口长度的时候，直接用 i-left 即可，用来更新结果 res 。
代码实现 class Solution {public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = -1, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
拓展
此题也可以使用滑动窗口的概念来处理。
建立一个 256 位大小的整型数组 freg ，用来建立字符和其出现位置之间的映射。
维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
（1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；
（2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
（3）重复（1）（2），直到左边索引无法再移动；
（4）维护一个结果 res，每次用出现过的窗口大小来更新结果 res ，最后返回 res 获取结果。
动画描述