定义

• 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储；
• ES6 中有字典，Map 数据结构；
• 字典的常用操作：键值对的增删改查；

const m = new Map()

// 增
m.set('a', 'aa')
m.set('b', 'bb')

// 查
const b = m.get('b')

// 删
m.delete('a')
// 清空
// m.clear()

// 改
m.set('b', 'abab')

使用场景

算法题：两个数组的交集

• 描述：给定两个数组，编写一个函数来计算它们的交集。

https://leetcode-cn.com/problems/intersection-of-two-arrays/

• 解题思路：求交集，用字典建立一个映射关系，记录 nums1 里有的值；然后遍历 nums2，找出 nums1 里也有的值。

• 解题步骤：新建一个字典，遍历 nums1，填充字典。然后遍历 nums2，遇到字典里的值就选出，并从字典中删除；

• 代码：

/**
 * @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
};

算法题：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

https://leetcode-cn.com/problems/valid-parentheses/

var twoSum = function(nums, target) {
    const hasMap = new Map()

    for(let i = 0; i < nums.length; i ++) {
        if(hasMap.has(target-nums[i])) {
            return [i, hasMap.get(target-nums[i])] 
        } else {
            hasMap.set(nums[i], i)
        }
    }
};

算法题：无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

• 解题思路：先找出所有的不包含重复字符的子串，然后找出长度最大那个子串，返回其长度即可。
• 解题步骤：用双指针维护一个滑动窗口，用来剪切子串。不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。过程中，记录所有窗口的长度，并返回最大值。

var lengthOfLongestSubstring = function(s) {
    let l = 0;
    let res = 0;
    const map = new Map()
    for (let r = 0; r < s.length; r+=1) {
        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
};

算法题：最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

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

• 解题思路：先找出所有的包含 T 的子串，然后找出长度最小的那个子串，返回即可。
• 解题步骤：用双指针维护一个滑动窗口，然后移动有指针，找到包含 T 的子串，移动左指针，尽量减少包含 T 的子串的长度。

/**
 * @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 newRfs = s.substring(l, r + 1);
            if (!res || newRfs.length < res.length) res = newRfs;
            // 左指针当前的字符
            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
};

阅读量：

评 论：