前言

在前端日新月异的大背景下， ES6 也基本已经覆盖性地全民普及。而数据结构集合和字典，也被运用于 ES6 的语法当中。 ES6 通过使用 Set 和 Map 这两个函数，来实现集合和字典的思想。而集合和字典，又是怎么被灵活应用的呢？

下面的这篇文章中，将带领大家来一起了解集合和字典在前端中应用，并使用 Map 和 Set 来实现前端的一些常见场景。一起来学习吧~🙋‍♀️

一、📝 集合

1、集合是什么？

集合是一种无序且唯一的数据结构；
ES6 中有集合，名为 Set ；
集合的常用操作： 去重、判断某元素是否在集合中、求交集……

2、前端与集合：使用 ES6 中的 Set

ES6 中的 Set 可以做什么呢？

使用 Set 对象： new 、 add 、 delete 、 has 、 size
迭代 Set ：多种迭代方法、 Set 与 Array 互转、求并集/交集/差集

3、用 Set 模拟并集、交集和差集

（1）模拟并集运算

我们可以创建一个函数，来返回包含 setA 和 setB 中所有元素的新集合。迭代这两个集合，并把所有元素都添加到并集的集合中。如下代码所示：

//模拟并集运算
const union = （setAe， setB) => {
    const unionab = new Set()
    setA.forEach(value => unionab.add(value))
    setB.forEach(value => unionab.add(value))
    return [...unionab]
}

console.log(union([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])) //[1, 2, 5, 8,9, 4, 10]

（2）模拟交集运算

模拟交集运算需要创建一个辅助函数，来生成包含 setA 和 setB 两个集合中共同拥有元素的新集合。具体代码如下：

// 模拟交集运算
const intersection = (setA, setB) => {
  const intersectionSet = new Set();
  const arrSetB = new Set(setB);
  setA.forEach((value) => {
    if (arrSetB.has(value)) {
      intersectionSet.add(value);
    }
  });
  return [...intersectionSet];
};

console.log(intersection([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])); //[5,8,9]

（3）模拟差集运算

差集运算是创建集合 setA 有，而集合 setB 没有的元素。简单来说，就是 setA 减去和 setB 相交的部分，剩余的部分即是差集的部分。

// 模拟差集运算
const difference = (setA, setB) => {
  const differenceSet = new Set();
  const arrSetB = new Set(setB);
  setA.forEach((value) => {
    if (!arrSetB.has(value)) {
      differenceSet.add(value);
    }
  });
  return [...differenceSet];
};

console.log(difference([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])); //[1, 2]

4、使用扩展运算符来模拟并集、交集和差集

上面我们实现了用 Set 来模拟并集、交集和差集，但这似乎有一点点冗余，如果遇到数据量大的时候还每一次都要执行这么多行代码，似乎这样子听起来就那么友好了。

因此，我们引入了一种新的方法来解决，ES6 的扩展运算符。

如果使用扩展运算符来进行运算的话，整个过程只需要三个步骤：

将集合转化为数组；
执行需要的运算；
将结果转化回集合。

接下来我们就用扩展运算符，来一一实现并集、交集和差集。

（1）用扩展运算符实现并集

来看下面一段代码：

// 模拟并集运算
const union = (setA, setB) => {
  return new Set([...setA, ...setB]);
};
console.log(union([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])); //[1, 2, 5, 8,9, 4, 10]

通过以上代码我们可以看到，使用扩展运算符，只需要短短一行代码，即可实现具体的并集运算，这样看起来简洁了许多。

接下来我们继续用这种方法，来实现交集和差集。

（2）用扩展运算符实现交集

// 模拟交集运算
const intersection = (setA, setB) => {
  const arrB = new Set(setB);
  return [...new Set([...setA].filter((x) => arrB.has(x)))];
};
console.log(intersection([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])); //[5, 8, 9]

与并集一样的效果，运用扩展运算符，很简洁的就实现了交集的功能。

（3）用扩展运算符实现差集

// 模拟差集运算
const difference = (setA, setB) => {
  const arrB = new Set(setB);
  return [...new Set([...setA].filter((x) => !arrB.has(x)))];
};
console.log(difference([1, 2, 5, 8, 9], [4, 5, 8, 9, 10])); //[1, 2]

同样地，使用扩展运算符的方法，但与交集相反的是，交集是筛选出集合 setB 拥有的元素，而差集是筛选出集合 setB 没有的元素，从而最终达到具体效果。

5、leetcode 案例题分析

（1）leetcode349 两个数组的交集

1）题意

这里附上原题链接

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

输入输出示例：

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
解释:
- nums1 和 nums2 两个数组的相交部分为 [9, 4] 。

2）解题思路

求交集且无序唯一。
使用集合。

3）解题步骤

用集合对 nums1 去重。
遍历 nums1 ，筛选出 nums2 中也包含的值。

4）代码实现

/**
 * @param {Array} nums1 数组1
 * @param {Array} nums2 数组2
 * @returns
 */
let intersection = function (nums1, nums2) {
  // 先进行数组去重
  const arr1 = new Set(nums1);
  const arr2 = new Set(nums2);

  // 过滤掉arr1在arr2中已经有的元素，过滤结果即为交集
  // has可改为includes
  const arr3 = [...arr1].filter((item) => arr2.has(item));

  return arr3;
};
console.log(intersection([1, 2, 3, 4], [4, 6, 8]));

二、📂 字典

1、字典是什么？

字典与集合相似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。
注意：字典一定是以键值对的形式存储！！

2、前端与集合：使用 ES6 中的 Map

ES6 中的 Map 可以做什么呢？

使用 Map 对象： new 、 set 、 delete 、 clear ；
字典的常用操作，键值对的增删改查。

3、使用 Map 类的 API

下面展示一段代码，来展示 map 的相关 API 。

const map = new Map();

//增
map.set('monday', '星期一');
map.set('Tuesday', '星期二');
map.set('Wednesday', '星期三');

console.log(map.has('monday')); //true
console.log(map.size); //3
console.log(map.keys()); //输出{'monday', 'Tuesday', 'Wednesday'}
console.log(map.values()); //输出{'星期一', '星期二', '星期三'}
console.log(map.get('monday')); //星期一

//删
map.delete('monday');

//清空
map.clear();

//改
map.set('monday', '星期四');

4、leetcode 案例题分析

（1）leetcode349 两个数组的交集

1）题意

这里附上原题链接

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

输入输出示例：

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
解释:
- nums1 和 nums2 两个数组的相交部分为 [9, 4] 。

2）解题思路

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

3）解题步骤

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

4）代码实现

/**
 * @param {Array} nums1 数组1
 * @param {Array} nums2 数组2
 * @returns
 */
let intersection = function (nums1, nums2) {
  // 先建立一个字典
  const map = new Map();
  // 遍历nums1的每一个，并放入数组中
  nums1.forEach((n) => {
    map.set(n, true);
  });

  const res = [];
  // 遍历nums2中的每一个
  nums2.forEach((n) => {
    // 与nums1中的对比，如果一样则push进res
    if (map.get(n)) {
      res.push(n);
      map.delete(n);
    }
  });
  return res;
};

console.log(intersection([1, 2, 2, 1], [2, 2]));

（2）leetcode20 有效地括号

1）题意

这里附上原题链接

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

输入输出示例：

输入: s = "()[]{}"
输出: true
解释:
- 左括号和右括号对应开闭。

2）解题步骤

判断字符串的个数是否为偶数，不是则直接返回。
建立一个字典，分别将三个括号映射进入。
遍历字符串。
遍历 nums1 ，筛选出 nums2 中也包含的值。

3）代码实现

/**
 *
 * @param {String} s 括号字符串
 * @returns boolean
 */
let 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++) {
    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;
};

console.log(isValid('[]')); //true
console.log(isValid('(]')); //false
console.log(isValid('([)]')); //false

（3）leetcode1 两数之和

1）题意

这里附上原题链接

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入输出示例：

输入: nums = [2,7,11,15], target = 9
输出: [0,1]
解释:
- 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

2）解题思路

把 nums 想象成相亲者；
把 target 想象成匹配条件；
用字典建立一个婚姻介绍所，存储相亲者的数字和下标。

3）解题步骤

新建一个字典作为婚姻介绍所；
nums 的值，逐个来介绍所找的对象，没有合适的就先登记，有合适的就牵手成功；
键值对，键 key 代表此对象的值，值 value 代表对象的联系方式，即下标。

4）代码实现

/**
 *
 * @param {Array} nums 数组
 * @param {Number} target 目标和
 * @returns []
 */
let twoSum = function (nums, target) {
  const map = new Map();
  for (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);
    }
  }
  return '没有目标匹配';
};

console.log(twoSum([1, 2, 3, 4], 6)); //[1, 3]

（4）leetcode3 无重复字符的最长子串

1）题意

这里附上原题链接

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

输入输出示例：

输入: s = "abcabcbb"
输出: 3
解释:
- 因为无重复字符的最长子串是 "abc" ，所以其长度为 3 。
2）解题思路
- 先找出所有的不包含重复字符的子串。
- 找出长度最大的那个子串，返回其长度即可。
3）解题步骤
- 用双指针维护一个滑动窗口，用来剪切子串。
- 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
- 过程中，记录所有窗口的长度，并返回最大值。

4）代码实现

/**
 * @param {string} s
 * @return {number}
 */
let lengthOfLongestSubstring = function (s) {
  let l = 0;
  let res = 0;
  const map = new Map();
  for (let r = 0; r < s.length; r++) {
    // map.get(r) >= l 确保下标在左指针右边
    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;
};

console.log(lengthOfLongestSubstring('ssdfsf')); // 3

（5）leetcode76 最小覆盖子串

1）题意

这里附上原题链接

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

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

输入输出示例：

输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
解释:
- BANC 覆盖 ABC 三个字母，并且是最小子串。

2）解题思路

先找出所有包含 T 的子串。
找出长度最小的那个子串，返回即可。

3）解题步骤

用双指针维护一个滑动窗口。
移动右指针，找到包含 T 的子串，移动左指针，尽量减少包含 T 的子串的长度。

4）代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
let minWindow = function (s, t) {
  // 用双指针维护一个滑动窗口
  // 指针初始位置都在第一个位置，即下标索引为0
  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) {
      // 打印滑动窗口及表示的子串
      // substring方法遵循左闭右开原则
      // console.log(s.substring(l, r + 1));
      const newRes = s.substring(l, r + 1);
      // 找出最小的子串
      if (!res || newRes.length < res.length) {
        res = newRes;
      }
      // c2代表左指针当前的字符
      const c2 = s[l];
      // 如果左指针在需求列表里面
      if (need.has(c2)) {
        // 字符的需求数量就需要增加
        need.set(c2, need.get(c2) + 1);
        // 如果字符需求数量为1，原来是0，现在是1，那么就重新需要此字符
        if (need.get(c2) === 1) {
          needType += 1;
        }
      }
      l += 1;
    } //当跳出while循环时，意味着左指针不能再移动，要开始移动右指针
    // 右指针移动则递增1
    r += 1;
  }
  return res;
};

console.log(minWindow('ASDFFGFGCX', 'AFG')); // ASDFFG

前言 ​

一、📝 集合 ​

1、集合是什么？ ​

2、前端与集合：使用 ES6 中的 Set ​

3、用 Set 模拟并集、交集和差集 ​

（1）模拟并集运算 ​

（2）模拟交集运算 ​

（3）模拟差集运算 ​

4、使用扩展运算符来模拟并集、交集和差集 ​

（1）用扩展运算符实现并集 ​

（2）用扩展运算符实现交集 ​

（3）用扩展运算符实现差集 ​

5、leetcode 案例题分析 ​

（1）leetcode349 两个数组的交集 ​

二、📂 字典 ​

1、字典是什么？ ​

2、前端与集合：使用 ES6 中的 Map ​

3、使用 Map 类的 API ​

4、leetcode 案例题分析 ​

（1）leetcode349 两个数组的交集 ​

（2）leetcode20 有效地括号 ​

（3）leetcode1 两数之和 ​

（4）leetcode3 无重复字符的最长子串 ​

（5）leetcode76 最小覆盖子串 ​

前言

一、📝 集合

1、集合是什么？

2、前端与集合：使用 ES6 中的 Set

3、用 Set 模拟并集、交集和差集

（1）模拟并集运算

（2）模拟交集运算

（3）模拟差集运算

4、使用扩展运算符来模拟并集、交集和差集

（1）用扩展运算符实现并集

（2）用扩展运算符实现交集

（3）用扩展运算符实现差集

5、leetcode 案例题分析

（1）leetcode349 两个数组的交集

二、📂 字典

1、字典是什么？

2、前端与集合：使用 ES6 中的 Map

3、使用 Map 类的 API

4、leetcode 案例题分析

（1）leetcode349 两个数组的交集

（2）leetcode20 有效地括号

（3）leetcode1 两数之和

（4）leetcode3 无重复字符的最长子串

（5）leetcode76 最小覆盖子串