字典

• 与集合类似，字段也是一种存储唯一值的数据结构吗，但是他是以键值对的形式来存储
• ES6中增加了字段，也就是Map

let a = new Map([ // 默认值
  ['a', 'aa']
])
a.set('b', 'bb') // 加入值

a.delete('b', 'bb') // 删除
a.set('a', 'aaa') // 替换值

console.log(a.get('a'), a.get('b')); // 读取值

题目 两个数组的交集

时间复杂度：O(n)

空间复杂度：O(n)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
  // 集合的方式
  // return [...new Set(nums1.filter(e => nums2.includes(e)))]
  
  // 字典的方式
  const map = new Map();
  nums1.forEach(e => {
    map.set(e, true)
  })
  const res = []
  nums2.map(e => {
    if (map.get(e)) {
      res.push(e)
      map.delete(e)
    }
  })
  return res
};

题目 有效的括号

时间复杂度：O(n)

空间复杂度：O(n)

/**
 * @param {string} s
 * @return {boolean}
 */

var isValid = function (s) {
  const stack = []
  var map = new Map([
    ['(', ')'],
    ['{', '}'],
    ['[', ']'],
  ])
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      stack.push(s[i])
    } else {
      if (map.get(stack[stack.length - 1]) === s[i]) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
};

题目 两数之和

时间复杂度：O(n)

空间复杂度：O(n)

思路： 循环中每次判断map中，是否存在匹配项，如果没有，加入到map中，等到被匹配，如果匹配到了，直接返回被匹配到的与当前元素

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    let e = nums[i]
    let n = target - e
    if (map.has(n)) {
      return [map.get(n), i]
    } else {
      map.set(e, i)
    }
  }
};

题目 无重复字符的最长子串

时间复杂度：O(n)

空间复杂度：O(n)

思路：使用双指针 + 字典的方式实现，就像剪切视频时候的滑动窗口一张 右边指针不断向前，每次向前的时候，判断当前窗口中是否存在已有元素，如果存在，就将左边指针调整到存在的问题

同时每次都判断滑动窗口的长度，最终获取到最长子串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let res = 0 // 最长长度
  let a = 0 // 滑动窗口起点
  const map = new Map() // 存储字符的字典
  for (let b = 0; b < s.length; b++) {
    const e = s[b];
    if (map.has(e) && map.get(e) >= a) {
      // 如果存在重复元素
      // 如果是abba 这样的情况,需要防止滑动窗口起始点变小,已经在滑动窗口外面了,不应当考虑
      a = map.get(e) + 1 // 滑动窗口左边前进一位
    }
    map.set(e, b) // 存储当前值的最后的下标 用于下次计算起始点
    res = Math.max(res, b - a + 1) // 当前长度与已知最大长度
  }
  return res
}

题目 最小覆盖子串（困难）

https://leetcode-cn.com/problems/minimum-window-substring/

时间复杂度：O(n2)

空间复杂度：O(n)

思路: 采用字典 + 双指针滑动窗口来实现最小覆盖子串的查找，因为题目不限制子串被覆盖的顺序，所以首先将子串通过Map结构转化为 数值:数量（abc => {‘a’ => 1,’b’ => 1,’c’ => 1 }）

​ 完成了Map的构建后，开始滑动右指针，知道map中数据都为0，代表当前滑动窗口覆盖了最小子串，这时候再开始左指针的滑动，知道左指针当前值在Map中，代表已经无法覆盖最小子串，此时左指针停止，再次开始滑动右指针，再次进入循环

​ 最后在每次滑动左边指针的时候，截取当前的最小覆盖子串，最后得到最小覆盖子串

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
 var minWindow = function (s, t) {
  
  // 最小子串大于字符串s，毕竟不存在最小子串，直接返回空
  if(t.length > s.length) {
    return ''
  }
  
  let start = 0 // 指针开头
  let end = 0 // 指针结尾
  let result = '' // 存储最小覆盖子串

  const need = new Map() // 存储最小子串数据
  for (let i = 0; i < t.length; i++) {
    const e = t[i];
    need.set(e, need.has(e) ? need.get(e) + 1 : 1)
  }
  // need 为 "ABC" =>  {'A' => 1,'B' => 1,'C' => 1 }
  let needType = need.size // 最小子串的长度,用于记录滑动窗户口还未包含几位数 

  // 先走后指针
  while (end < s.length) {
    const c = s[end] // 滑动窗口右边向前
    if (need.has(c)) { // 判断当前元素是否在map中
      need.set(c, need.get(c) - 1) // 如果在map中,其值减1
      if (need.get(c) == 0) {
        // 如果当前值,在map中为0了,说明当前滑动窗口包含了当前值的所有数量
        // 所以对记录map数量的数值再减1
        needType -= 1
      }
    }
    // 如果needType为0了,说明次数滑动窗口已经包含所有子串
    while (needType === 0) {
      // 获取当前子串
      let carry = s.substring(start, end + 1)
      // 对比存储子串与当前子串,获取最小的
      if (result == '' || result.length > carry.length) {
        result = carry
      }
      const c2 = s[start]
      if (need.has(c2)) {
        // 判断当前元素是否在map中,在,这说明某个值移出了,此时已经不是最小子串,因此map中的当前值,+1
        // 因为去除了存在的值,当前子串已经不符合标准,needType记录值+1
        // 左指针停止,开始右指针行动,知道它再次覆盖了子串
        need.set(c2, need.get(c2) + 1)
        if (need.get(c2) === 1) {
          needType += 1
        }
      }
      start += 1 // 左指针前进
    }
    end += 1 // 右指针前进
  }
  return result
};