哈希
解题思路
定义两个 hash 数据结构的 Set 集合，对 nums1 去重放入第一个 hash 并和 nums2 对比是否存在交集；
将交集的部分放入 第二个 Set 集合 并返回；
复杂度
-
时间复杂度：
O(m+n)，其中 m 和 n 分别是两个数组的长度，需要遍历两个数组并对哈希表进行操作； -
空间复杂度：
O(m+n)，其中 m 和 n 分别是两个数组的长度，空间复杂度主要取决于两个集合；
代码实现
function intersection(nums1: number[], nums2: number[]): number[] {
const hash = new Set(nums1);
const res = new Set();
for (let i = 0; i < nums2.length; i++) {
if (hash.has(nums2[i])) {
res.add(nums2[i]);
}
}
return [...res] as unknown[]as number[];
};
排序 + 双数组双指针
解题思路
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集；
首先对两个数组进行排序，然后使用两个指针遍历两个数组；
- 初始时，两个指针分别指向两个数组的头部；
- 每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位；
- 如果两个数字相等，还需判断结果数组中是否存在，不存在则将该数字添加到结果数组中，并将两个指针都右移一位；
- 当至少有一个指针超出数组范围时，遍历结束；
复杂度
-
时间复杂度：
O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度； -
空间复杂度：
O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度，空间复杂度主要取决于排序使用的额外空间；
代码实现
var intersection = function (nums1, nums2) {
const res = [];
let inx1 = 0;
let inx2 = 0;
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
while (inx1 < nums1.length && inx2 < nums2.length) {
if (nums1[inx1] === nums2[inx2] && nums1[inx1] !== res[res.length - 1]) {
res.push(nums1[inx1]);
inx1++;
inx2++;
} else if (nums1[inx1] > nums2[inx2]) {
inx2++;
} else {
inx1++;
}
}
return res;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 350. 两个数组的交集 II
上一篇
评论
