JavaScript版：数据结构之“字典”
1. 字典简介
与集合类似，字典也是一种存储唯一值的数据结构，但它是以
键值对的形式来存储。使用
ES6 Map
1.1 字典的常用操作
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 解题思路
输入：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. 无重复字符的最长子串
6. LeetCode: 76. 最小覆盖子串
7. 总结：
与集合类似，字典也是一种存储唯一值的数据结构，但是它以
键值对的形式来存储ES6中有字典，名为Map
字典的常用操作：键值对的增删改查
作者：服部
链接：https://juejin.cn/post/7023981920425869326