1.字典简介

1. 字典是什么？
   解答：与集合类似，也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。(键值对是最重要的特性)
2. 在Es6中新增了字典，名为Map
3. 字典的常用操作：增删改查

const map = new Map()// 新增
map.set('a', 'aa')
map.set('b', 'bb')
map.set('c', 'cb')// 删除
map.delete('a')// 清空
// map.clear()// 改
map.set('b', 'bbb')// 查 (get方法读取key对应的键值，如果找不到key，返回undefined。)
map.get('a')// has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。
map.has('a')

遍历方法
Map 结构原生提供三个遍历器生成函数和一个遍历方法。Map.prototype.keys()：返回键名的遍历器。
Map.prototype.values()：返回键值的遍历器。
Map.prototype.entries()：返回所有成员的遍历器。
Map.prototype.forEach()：遍历 Map 的所有成员。

leetCode: 349.两个数组的交集

var intersection = function (nums1, nums2) {var map = new Map()nums.forEach(item => {map.set(item, true)})const res = []nums2.forEach(n => {if (map.get(n)) {res.push(n)// 找到之后需要从字段中删除，目的：为了防止数据重复map.delete(n)}})return res
}时间复杂度：nums1 + nums2
空间复杂度：字典的空间复杂度 O(m)

leetCode： 20.有效的括号

优化

function leftEqualRight = function (left, right) {if(left === '(' && right === ')') return trueif(left === '{' && right === '}') return trueif(left === '[' && right === ']') return truereturn false
}const isVlaid = function (s) {// 判断s的字符传长度是否为奇数if (s.length % 2 === 1) return falseconst stack = []// 创建字典const map = new Map()map.set('(', ')')map.set('[', ']')map.set('{', '}')for (var i = 0; i < s.length; i++) {const c = s[i]if (map.has(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
}时间复杂度：o(n)
空间复杂度：o(n)

leetCode1.两数之和

给定一个数组nums，和一个目标值target，请你在该数组中找出和为目标值的那2个整数，，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，但是，数组中同一个元素不能使用2遍。
例如：nums = [2,7,11,15], target = 9
因为:nums[0] + nums[1] = 2 + 7 = 9
所以返回：[0, 1]

const twoSum = function (nums, target) {const map = new Map()for (let i = 0; i < nums.length;i++) {const n = nums[i]const n2 = target - nif (map.has(n2)) {return [map.get(n2), i]} else {map.set(n, i)}}
}时间复杂度：O(n)
空间复杂度：O(n) * 3

leetCode： 3.无重复字符的最长子串？

给定一个字符串，找出其中不含有重复字符的最长子串的长度。
例如：‘abcabcbb’, 输出3，解释：因为无重复字符的最长子串是‘abc’，所以其长度是3

所谓的双指针：其实就是2个变量，用变量来记录剪切子串的起始位置。
过程：两个指针分别叫左指针，右指针，在下标为0的位置，先移动右指针，右指针每移动一位就和左指针对比一下看是否相等，如果不相等，右指针继续移动，如果相等，则左指针移动到重复字符的下一位。这样就可以保证所有的子串都是不包含重复字符的。在移动过程中记录所有子串的长度。

var maxlength = function(s) {// 左指针let l = 0// 右指针需要不断移动，因此写个循环，在遍历的过程中不断的记录右指针let res = 0const map = {}for (let i = 0; i < s.length; i++) {// 如果遇到重复字符if (map.has(s[i]) && map.get(s[i] >= l)) {// 左指针则向下移动一位l = map.get(s[i]) + 1}res = Math.max(res, r - l + 1)map.set(s[r], i)}}
时间复杂度：O(n)
空间复杂度：O(m) m :不重复字符的个数

leetCode: 76.最小覆盖子串?

给你一个字符串s，一个字符串t，请在字符串s里面找出：包含t所有字符串的最小子串。
例如：s=“ADDBECODEBANC” , t=“ABC”
输出：“BANC”

如果s中不存在，则返回"",

如果存在，则要保证它是唯一的答案。

const 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)}// 使用循环移动右指针的位置while(r < s.length) {const c = s[r]if (need.has(c)) {need.set(c, need.get(c) - 1)}r += 1}
}

总结

1. 与集合类似，也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。(键值对是最重要的特性)
2. 在Es6中新增了字典，名为Map
3. 字典的常用操作：键值对的增删改查