1. 字典简介
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以
键值对的形式来存储。 - 使用
ES6 Map
1.1 字典的常用操作
代码语言：javascript复制const m = new Map();
// 增
m.set('a', 'aa');
m.set('b', 'bb');
// 删
m.delete('b');
m.clear();
// 改
m.set('a', 'aaa')
// 查
m.get('a');2. LeetCode： 349. 两个数组的交集
在这里插入图片描述2.1 解题思路
- 求nums1 和 nums2 多都有的值
- 用字典建立一个映射关系，记录nums1里有的值
- 遍历nums2,找出nums1 里也有的值
2.2 解题步骤
- 新建一个字典，遍历nums1,填充字典
- 遍历nums2, 遇到字典里的值就选出，并从字典中删除。
/** * @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]} */
var intersection = function (nums1, nums2) {
// 集合Set 实现方式
// return [...new Set(nums1)].filter(item => nums2.includes(item))
const map = new Map();
nums1.forEach(n => {
map.set(n, true)
})
const res = [];
nums2.forEach(n => {
if (map.get(n)) {
res.push(n);
map.delete(n);
}
})
return res
};3. LeetCode：20. 有效的括号
在这里插入图片描述/** * @param {string} s
* @return {boolean} */
var isValid = function (s) {
if (s.length % 2 === 1) { return false }
const stack = [];
const map = new Map();
map.set('(', ')')
map.set('[', ']')
map.set('{', '}')
for (let i = 0; i < s.length; i = 1) {
const c = s[i];
if (c === '(' || c === '{' || c === '[') {
stack.push(c)
} else {
const t = stack[stack.length - 1];
if (
map.get(t) === c
) {
stack.pop();
} else {
return false;
}
}
}
return stack.length === 0;
};参考视频：传送门
4. LeetCode: 1. 两数之和
在这里插入图片描述4.1 解题思路
代码语言：javascript复制输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] nums[1] == 9 ，返回 [0, 1] 。- 把nums 想象成相亲者
- 把target 想象成匹配条件
- 用字典建立一个婚姻介绍所，存储相亲者的数字和下标
4.2 解题步骤
- 新建一个字典作为婚姻介绍所
- nums 里的值，逐个来介绍找对象，没有何止的就先登记者，有合适的就牵手
/** * @param {number[]} nums
* @param {number} target
* @return {number[]} */
var twoSum = function (nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i = 1) {
const n = nums[i];
const n2 = target - n;
if (map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
};执行用时：56 ms, 在所有 JavaScript 提交中击败了99.77%的用户
内存消耗：39.9 MB, 在所有 JavaScript 提交中击败了37.04%的用户
内存消耗为 O(n), 我们可以通过二分查找，用时间换空间的方式，进行处理
5. LeetCode: 3. 无重复字符的最长子串
5.1 题目描述
在这里插入图片描述5.2 解题步骤
- 用双指针维护一个滑动窗口，用来剪切子串
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
- 过程中，记录所有窗口的长度，并返回最大值。
5.3 代码实现
代码语言：javascript复制/** * @param {string} s
* @return {number} */
var lengthOfLongestSubstring = function (s) {
let l = 0; // 左指针位置
let res = 0; // 定义返回结果
const map = new Map();
for (let r = 0; r < s.length; r = 1) {
// r 右指针位置
if (map.has(s[r]) && map.get(s[r]) >= l) {
l = map.get(s[r]) 1;
}
res = Math.max(res, r - l 1)
map.set(s[r], r)
}
return res;
};- 时间复杂度 O(n)
- 空间复杂度 O(m)
6. LeetCode: 76. 最小覆盖子串
6.1 题目描述
在这里插入图片描述6.2 解题思路
- 先找出所有包含T的子串
- 找出长度最小的那个子串，返回即可
6.3 解题步骤
- 用双指针维护一个滑动窗口。
- 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度。
6.3 代码实现
代码语言：javascript复制/** * @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 needType = need.size;
let res = '';
while (r < s.length) {
const c = s[r];
if (need.has(c)) {
need.set(c, need.get(c) - 1);
if (need.get(c) === 0) needType -= 1;
}
while (needType === 0) {
const newRes = s.substring(l, r 1);
if(!res || newRes.length < res.length) res = newRes;
const c2 = s[l]
if (need.has(c2)) {
need.set(c2, need.get(c2) 1)
if (need.get(c2) === 1) needType = 1;
}
l = 1;
}
r = 1;
}
return res
};- 时间复杂度 O(m n),m 是t的长度，n是s的长度
- 空间复杂度 O(m)
7. 总结：
- 与集合类似，字典也是一种存储唯一值的数据结构，但是它以
键值对的形式来存储 - ES6中有字典，名为Map
- 字典的常用操作：键值对的增删改查
