字典是什么？
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
- ES6中有字典，名为Map
- 字典的常用操作：键值对的增删改查
const m = new Map();
// 增
m.set('a', 'aa'); // key : value
m.set('b', 'bb');
// 删
m.delete('b');
// m.clear(); // 删除所有
// 改
m.set('a', 'aaaa')
// 查
m.get('a')LeetCode #349 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
- 输入：nums1 = [1,2,2,1], nums2 = [2,2]
- 输出：[2]
示例 2：
- 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
- 输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
解题思路：
- 求nums1和nums2都有的值
- 用字典建立一个映射关系，记录nums1里有的值
- 遍历nums2，找出nums1里边也有的值
解题步骤：
- 新建一个字典，遍历nums1，填充字典
- 遍历nums2，遇到字典里的值就选出，并从字典里删除（防止重复）
复杂度：
- 时间复杂度：O（m+n）
- 空间复杂度：O（m）
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
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;
};LeetCode #20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
- 输入: "()"
- 输出: true
示例 2:
- 输入: "()[]{}"
- 输出: true
示例 3:
- 输入: "(]"
- 输出: false
示例 4:
- 输入: "([)]"
- 输出: false
示例 5:
- 输入: "{[]}"
- 输出: true
解题思路：
利用map建立括号的字典集
将之前的复杂的判断条件改写
解题步骤：
复杂度：
1.时间复杂度：O（n）
2.空间复杂度：O（n）
/**
* @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(map.has(c)){
stack.push(c);
}else{
const top = stack[stack.length-1];
if(
map.get(top) === c
){
stack.pop();
}else{
return false;
}
}
}
return stack.length === 0;
};LeetCode #1 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
方法一：
var twoSum = function(nums, target) {
let result = []
for(let i=0; i<nums.length; i++){
for(let j=i+1; j<nums.length;j++){
if(nums[i]+nums[j] == target){
result.push(i)
result.push(j)
}
}
}
return result
};方法二：
/**
* @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++){
const n = nums[i]
const n2 = target-n;
if(map.has(n2)){
return [map.get(n2), i]
}else{
map.set(n, i);
}
}
};LeetCode #3 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 :
- 输入: "abcabcbb"
- 输出: 3
- 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 输入: "bbbbb"
- 输出: 1
- 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
- 输入: "pwwkew"
- 输出: 3
- 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题思路：
- 先找出所有的不包含重复字符的字串
- 找出长度最大那个字串，返回其长度即可
解题步骤：
- 用双指针维护一个滑动窗口，用来剪切字串
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
- 过程中，记录所有窗口的长度，并返回最大值
复杂度：
- 时间复杂度 O（n）
- 空间复杂度 O（m）m即字符串中不重复的个数
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 左右指针
let left = 0;
let res = 0;
const map = new Map();
for(let right=0; right<s.length; right++){
if(map.has(s[right]) && map.get(s[right]) >= left){ // 如果遇到重复字符，左指针移动到右指针下一位 && map中的重复字符下标必须在窗口中
left = map.get(s[right]) + 1;
}
res = Math.max(res, right - left + 1); // 新窗口的右指针与res的较大值
map.set(s[right], right);
}
return res;
};LeetCode #76 最小覆盖子串【Hard】
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 ：
- 输入：s = "ADOBECODEBANC", t = "ABC"
- 输出："BANC"
- 输入：s = "a", t = "a"
- 输出："a"
提示：
- 1 <= s.length, t.length <= 105
- s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
解题思路：
- 先找出所有的包含T的字串
- 找出长度最小的那个字串，返回
解题步骤：
- 用双指针维护一个滑动窗口，用来枚举所有子串
- 移动右指针，找到包含T的字串，移动左指针，尽量减少包含T的子串的长度
复杂度：
- 时间复杂度 O（n+m）n是s的长度, m是t的长度
- 空间复杂度 O（m）m是t里边不同字符的个数
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
// 创建左右指针
let left = 0;
let right = 0;
const need = new Map();
for(let c of t){
need.set(c, need.has(c) ? need.get(c) + 1 :1);
}
// console.log(need);
let needType = need.size;
let res = '';
// 移动右指针
while(right < s.length){
const c = s[right] // 获取右指针当前的字符
if(need.has(c)){ // 如果右指针在我们当前的列表里面
need.set(c, need.get(c)-1); // need中要减去1
// 满足t所有的都在need
if(need.get(c) === 0){
needType -= 1;
}
}
while(needType === 0){ // 缩小字符串范围
// console.log(s.substring(left, right+1)) // 所有子串
const newRes = s.substring(left, right+1)
if(!res || newRes.length < res.length){ // 找出长度最小的子 如果res为空 则先赋值给它newRes
res = newRes;
}
const c2 = s[left]; //左指针当前的字符
if(need.has(c2)){
need.set(c2, need.get(c2)+1); // 需求增加
if(need.get(c2) === 1){ // 重新需要这个字符
needType += 1; // 更新needtype
}
}
left += 1;
}
right += 1;
// 判断移动右指针时，滑动窗口（子串）包含t的所有字符：用字典
}
return res
};字典-章节总结
- 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
- ES6中有字典，名为Map（映射）
- 字典的常用操作：键值对的增，删，改，查
思考
在实际工作中使用字典完成一次映射操作的场景
有一次需求需要自己对DOM树进行遍历，由于遍历的规则可能导致重复访问节点，就用Map将访问过的DOM节点映射为true，然后处理节点前进行判断。
const visited = new Map(); visited.set(node, true); ... if (!visited.get(node)) { // 当前节点未访问过，进行处理 }用Chrome的Profile工具或者其他任意前端性能测试工具，测试Map和Object频繁增删操作的性能，谁高谁低？
Comments | NOTHING