1.什么是字典？
- 字典是一种以键值对的形式存储唯一值的数据结构
- ES6中有字典，名为Map
2.常用操作
- 添加元素 set
- 删除元素 delete
- 更改元素 set
- 查找元素 get
- 清空字典 clear
3.代码示例
//创建字典
const myMap = new Map();
//增,'a'为键，'aa'为值
myMap.set('a','1'); // {a:1}
myMap.set('b','2'); //{a:1,b:2}
//删
myMap.delete('b'); // {a:1}
//改
myMap.set('a','3'); //{a:3}
//查
let c = myMap.get('a'); // c = 3
//清除全部键值对
myMap.clear(); // {}
4.LeetCode
接下来使用字典这个数据结构来刷LeetCode有关字典的题目，巩固提升对字典的了解。
题号349.两个数组的交集（简单）
题目要求:
解题思路:
方法二: 使用字典
- 利用字典元素的唯一性，将数组一的值赋值给字典作为键
- 如果数组二的值出现在字典键中，则说明是相交的元素，压入栈中，删除字典中该元素，防止重复
编写代码：
var intersection = function(nums1, nums2) {
const map = new Map();
const res = [];
nums1.forEach(n => {
map.set(n,true);
})
nums2.forEach(m => {
if(map.get(m)) {
res.push(m);
map.delete(m);//防止重复
}
})
return res;
};
复杂度分析
- 时间复杂度: O(m+n)
- 空间复杂度: O(n)
题号3.无重复字符的最长子串（中等）
题目要求:
 >= l 用来预防窗口外字符等于当前右指针的情况，窗口外字符已经不属于当前滑动窗口，比如abba,执行到左指针为第二个b时，接着执行，左指针会跑到第一个a，这样就错误了
编写代码：
var lengthOfLongestSubstring = function(s) {
let l = 0;
let res = 0;
const map = new Map();
for(let r = 0; r < s.length; r++) {
if(map.has(s[r]) && map.get(s[r]) >= l) {
l = map.get(s[r]) + 1; // l移动到之前存储该元素位置的下一位，后面会再存储这个元素一次
}
res = Math.max(res,r-l+1);
map.set(s[r],r); //存储元素位置
}
return res;
};
复杂度分析
- 时间复杂度: O(n)
- 空间复杂度: O(m) ,m是字符串中不重复字符的个数
题号76.最小覆盖子串（困难）
题目要求:
解题思路:
思路:
- 用双指针维护一个滑动窗口
- 统计需要字符的种类和数量
- 移动右指针，找到包含T的子串
- 移动左指针，尽量减少包含T的子串的长度
- 循环上述过程，找到包含T的最小子串
编写代码：
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let l = 0;
let r = 0;
const need = new Map();
// 确定所要获取的各个字符的个数
for (let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
// 需要的类型数量等于字典长度
let needTypeCount = need.size;
// 定义一个要返回的字符串
let res = '';
while (r < s.length) {
// 获取右指针当前字符
const c = s[r];
// 判断是否是需要的字符，如果是，那就让需要的字符减一
if (need.has(c)) {
//need.get(c)变成负数的话就说明子串中多富裕几个字符，在移动左指针的时候加回来就可以
need.set(c,need.get(c) - 1);
// 如果当前需要的字符数量等于0，那就让当前需要类型数量减一
if (need.get(c) === 0) needTypeCount -= 1;
}
//如果需要的字符类型数量都等于0了，就说明满足题目要求的全部字符都出现了
while (needTypeCount === 0) {
//subStirng是左开右闭的,所以是r+1
const newRes = s.substring(l, r + 1);
//如果刚开始res是空字符串，就先给他赋值为newRes
if (!res || newRes.length < res.length) res = newRes;
// 温饱满足了，尝试奔小康，尝试减少字符串的长度，
const c2 = s[l];
// 如果当前左指针指向的是需要的字符，因为我们要尝试缩短字符串长度，移动左指针
// 所以设置需要当前这个字符数的数量加一
if (need.has(c2)) {
need.set(c2,need.get(c2) + 1);
//如果需要的字符数等于 1 说明子串不满足包含所有字母种类了 needTypeCount+1
if (need.get(c2) === 1) needTypeCount += 1;
}
l += 1;
}
r += 1;
}
return res;
};
复杂度分析
- 时间复杂度：O(m+n) m是t的长度，n是s的长度
- 空间复杂度: O(m) m是t中不同字符的个数