# 两个数组的交集（349）
# 题目
给定两个数组，编写一个函数来计算它们的交集。
# 示例
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
# 说明
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
# 算法
# 排序 + 双指针
注意过滤掉重复元素
export const intersection = (nums1, nums2) => {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let i = 0,
j = 0;
const res = [];
while (i < nums1.length && j < nums2.length) {
while (nums1[i] === nums1[i + 1]) {
i++;
}
while (nums2[j] === nums2[j + 1]) {
j++;
}
if (nums1[i] === nums2[j]) {
res.push(nums1[i]);
i++;
j++;
continue;
}
if (nums1[i] < nums2[j]) {
i++;
continue;
}
if (nums1[i] > nums2[j]) {
j++;
continue;
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Set
遍历较小的Set（为了降低复杂度），然后看长度较大的Set中是否有这个元素，有则推入结果数组
export const intersection = (nums1, nums2) => {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let res = [];
if (set1.size > set2.size) {
const tempSet = set1;
set1 = set2;
set2 = tempSet;
}
for (const item of set1) {
if (set2.has(item)) {
res.push(item);
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Map
将第一个数组按照{number: true}放入Map，然后遍历第二个数组，如果是第一次遍历到存在于Map中的值，推入结果数组并将其在Map中的值设为false（标记为已存在于结果数组），之后如遍历到对应Map中值为false的数组元素则跳过。
export const intersection = (nums1, nums2) => {
let map = new Map();
let res = [];
for (const item of nums1) {
map.set(item, true);
}
for (const item of nums2) {
if (map.has(item) && map.get(item)) {
res.push(item);
map.set(item, false);
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# filter + includes
使用lastIndexOf判断是否是重复元素
export const intersection_4 = (nums1, nums2) => {
return nums1.filter((item, index) => nums2.includes(item) && nums1.lastIndexOf(item) === index);
};
1
2
3
2
3
# Set + filter + includes
先取交集再去重
export const intersection = (nums1, nums2) => {
return [...new Set(nums1.filter((item) => nums2.includes(item)))];
};
1
2
3
4
2
3
4