1. 字典简介
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 解题思路
2.2 解题步骤
/** * @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 解题步骤
/** * @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;};
复制代码
6. LeetCode: 76. 最小覆盖子串
6.1 题目描述
6.2 解题思路
先找出所有包含 T 的子串
找出长度最小的那个子串，返回即可
6.3 解题步骤
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};
复制代码
7. 总结：
评论