[leetcode] 349. 两个数组的交集

数组的交集"/>

[leetcode] 349. 两个数组的交集

代码

第一次

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {return [...new Set([...new Set(nums1)].filter(item => nums2.includes(item)))]
};

第二次

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {// 要求num1长度更短，num2长度更长if(nums1.length > nums2.length) {const _ = nums1nums1 = nums2nums2 = _}return [...new Set(nums2)].filter(item => nums1.includes(item))
};

提速原因：较长的数组用来做has或includes，短的数组用于遍历。

第三次

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {// 根据数组大小交换操作的数组if(nums1.length < nums2.length) {const _ = nums1;nums1 = nums2;nums2 = _;}const nums1Set = new Set(nums1);const resSet = new Set();// 循环 比 迭代器快for(let i = nums2.length - 1; i >= 0; i--) {nums1Set.has(nums2[i]) && resSet.add(nums2[i]);}return Array.from(resSet);
};

提速原因：循环比迭代器快！

第四次

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {let m = new Map()// 保证nums1是最长的if(nums1.length < nums2) {const box = nums1nums1 = nums2nums2 = box}// nums1自动去重for(let i = 0; i < nums1.length; i++) {m.set(nums1[i], true)}// 寻交集const res = []for(let i = 0; i < nums2.length; i++) {if(m.get(nums2[i])) {res.push(nums2[i])m.delete(nums2[i])}}return res
};

换个思路，使用字典解决。

时间空间复杂度

1. 时间复杂度：O(n²)或O(m*n)，m和n分别是遍历、has函数或includes函数
2. 空间复杂度：O(n)，去重后的长度

思路

2个遍历寻找相同元素。

总结

1. 循环比迭代器快。
2. 箭头函数只有一行函数体时，可省return、{}。
3. 算法要求时间复杂度、空间复杂度都低，那么例如本题，数组较短的可用于遍历，较长的数组可使用内置函数。