Links

0349. 两个数组的交集

题目地址(349. 两个数组的交集)

https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目描述

给定两个数组,编写一个函数来计算它们的交集。
 
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
 
说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

前置知识

  • hashtable

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

先遍历第一个数组,将其存到 hashtable 中,然后遍历第二个数组,如果在 hashtable 中存在就 push 到 ret,然后清空 hashtable,最后返回 ret 即可。

关键点解析

  • 空间换时间

代码

代码支持:JS, Python
Javascript Code:
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function (nums1, nums2) {
const visited = {};
const ret = [];
for (let i = 0; i < nums1.length; i++) {
const num = nums1[i];
visited[num] = num;
}
for (let i = 0; i < nums2.length; i++) {
const num = nums2[i];
if (visited[num] !== undefined) {
ret.push(num);
visited[num] = undefined;
}
}
return ret;
};
Python Code:
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
visited, result = {}, []
for num in nums1:
visited[num] = num
for num in nums2:
if num in visited:
result.append(num)
visited.pop(num)
return result
# 另一种解法:利用 Python 中的集合进行计算
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return set(nums1) & set(nums2)
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。