0349. 两个数组的交集
题目地址(349. 两个数组的交集)
题目描述
1
给定两个数组，编写一个函数来计算它们的交集。
2
3
4
5
示例 1：
6
7
输入：nums1 = [1,2,2,1], nums2 = [2,2]
8
输出：[2]
9
示例 2：
10
11
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
12
输出：[9,4]
13
14
15
说明：
16
17
输出结果中的每个元素一定是唯一的。
18
我们可以不考虑输出结果的顺序。
Copied!
前置知识
- hashtable
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
先遍历第一个数组，将其存到 hashtable 中，然后遍历第二个数组，如果在 hashtable 中存在就 push 到 ret，然后清空 hashtable，最后返回 ret 即可。
关键点解析
- 空间换时间
代码
代码支持：JS, Python
Javascript Code:
1
/**
2
* @param {number[]} nums1
3
* @param {number[]} nums2
4
* @return {number[]}
5
*/
6
var intersection = function (nums1, nums2) {
7
const visited = {};
8
const ret = [];
9
for (let i = 0; i < nums1.length; i++) {
10
const num = nums1[i];
11
12
visited[num] = num;
13
}
14
15
for (let i = 0; i < nums2.length; i++) {
16
const num = nums2[i];
17
18
if (visited[num] !== undefined) {
19
ret.push(num);
20
visited[num] = undefined;
21
}
22
}
23
24
return ret;
25
};
Copied!
Python Code:
1
class Solution:
2
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
3
visited, result = {}, []
4
for num in nums1:
5
visited[num] = num
6
for num in nums2:
7
if num in visited:
8
result.append(num)
9
visited.pop(num)
10
return result
11
12
# 另一种解法：利用 Python 中的集合进行计算
13
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
14
return set(nums1) & set(nums2)
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago