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. 无反复字符的最长子串
5.1 题目形容
5.2 解题步骤
- 用双指针保护一个滑动窗口，用来剪切子串
- 一直挪动右指针，遇到反复字符，就把左指针挪动到反复字符的下一位。
- 过程中，记录所有窗口的长度，并返回最大值。
5.3 代码实现
/** * @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 代码实现
/** * @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
- 字典的罕用操作：键值对的增删改查