集合

1. 是什么？

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

// 去重
const arr = [1,1,2,2]
const arr2 = [...new Set(arr)];

// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(3)

// 求交集
const set2 = new Set([2,3])
const set3 = new Set([...set].filter(item => set2.has(item)))

// 求差集
const set4 = new Set([...set].filter(item => !set2.has(item)))

2. 场景

2.1. 两个数组的交集 leetCode 349

给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

解题思路：

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

解题步骤：

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

var intersection = function(nums1, nums2) {
    return [...new Set(nums1)].filter(n => nums2.includes(n))
};

时间复杂度 filter 一次遍历是 O(n)，里面的 includes 又会遍历一遍又是 O(n) 所以是 O(n^2)
空间复杂度里面只声明了一个数组，所以 是 O(n)

Set 操作

遍历

var set = new Set([1,2,3])
set.add({a: 1,b:1})
for (let key of set) {
    console.log(key) // 1 2 3 {a: 1, b: 1}
}