本篇文章可以收获的知识：

  • 什么是字典
  • 字典的常用操作
  • 三道LeetCode算法题巩固字典
  • 如何分析时间复杂度和空间复杂度

什么是字典

字典与集合类似，字典也是一种存储唯一值的数据结构，但字典是以键值对的形式来存储，ES6中有字典，名为Map。

字典的常用操作

const m = new Map() // 字典
m.set("a", "b") // 给字典添加元素
m.set("a", "c") // 修改字典的某个元素
m.get("a") // 从字典中获取目标元素
m.delete("a") // 从字典中删除目标元素
m.clear() // 清空字典

LeetCode算法题：题号349，两个数组的交集

解题思路：

  • 用字典建立一个映射关系，记录nums1的值
  • 遍历nums2，找出nums1也有的值

解题步骤：

  • 新建一个字典，遍历nums1，填充字典
  • 遍历nums2，遇到字典里的值选出来，并从字典中删除

代码实现：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
  const nums3 = []
  const m = new Map()
  nums1.forEach(i => m.set(i, true))
  nums2.forEach(i => {
    if (m.get(i)) {
      nums3.push(i);
      m.delete(i)
    }
  })
  return nums3;
};

因为代码中有个循环，循环次数是数组的长度，所以时间复杂度是O(n)，n是数组的长度。

因为代码中使用了map数据结构，长度最大是数组的长度，所以空间复杂度是O(n)，n是数组的长度。

LeetCode算法题：题号1，两数之和

解题思路：

  • 把nums当成已婚人士（成员中可能有自己的对象，也有可能对象不在这个nums中）。
  • 把target当成寻找自己对象的目标
  • 用字典建立一个房间，存储已婚人士的值和下标

解题步骤：

  • 用字典建立一个房间
  • 遍历nums如果没有找到对象的保留在房间中，如果找到就结束

代码实现：

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

因为代码有一个for循环体，循环次数最大是nums的长度，所以时间复杂度是O(n)，n是数组的长度。

因为代码中用到map数据结构，最大长度是数组的长度，所以空间复杂度是O(n)，n是数组的长度。

LeetCode算法题：题号3，无重复字符串的最长字串

解题思路：

  • 找出所有没有重复的字符的子串
  • 找出长度最大的那个子串，返回其长度

解题步骤：

  • 用双指针维护一个滑动窗口，用来剪切子串
  • 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
  • 过程中记录所有窗口的最大长度

代码实现：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let l = 0
  let max = 0;
  const map = new Map()
  for (let r = 0; r < s.length; r ++) {
    if (map.has(s[r]) && map.get(s[r] >= l)) {
      l = map.get(s[r]) + 1
    }
    max = Math.max(max, r - l + 1)
    map.add(s[r], r)
  }
};

LeetCode算法题：题号76，最小覆盖子串

解题思路：

  • 找出所有覆盖的子串
  • 返回最小的子串

解题步骤：

  • 使用一前一后双指针维护一个窗口
  • 不断的移动右指针，当窗口中包含目标子串的时候，移动左指针
  • 当左指针对应的字符串在目标字符串中的时候，记录子串

代码实现：

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  let l = 0
  let m = new Map()
  let str = ""
  let type = 0

  for (let i = 0; i < t.length; i++) {
    m.set(t[i], 1)
  }
  for (let r = 0; r < s.length; r++) {
    const c = s[r]
    if (m.has(c)) {
      m.set(c, m.get(c) - 1)
      m.get(c) === 0 && (type += 1)
    }

    while (type === 3) {
      if (m.has(s[l])) {
        str = !str || r - l + 1 < str.length ? s.substr(l, r + 1) : str
        m.set(s[l], m.get(s[l]) + 1)
        m.get(s[l]) === 1 && (type -= 1)
      }
      l += 1
    }
  }
  return str
}

最后，希望读者可以通过本篇文章对字典有一定的认识和觉悟。。。。。。