What is the primary pattern for solving the Intersection of Two Arrays problem?

The primary pattern is array scanning combined with hash lookup, ensuring efficient identification of common elements while maintaining uniqueness.

How can I ensure my solution handles duplicates correctly?

Using a hash table or set will automatically remove duplicates, ensuring that each common element appears only once in the result.

Can this problem be solved with sorting?

While sorting could be used, it would increase the time complexity to O(n log n). The optimal approach is to use hash lookups for a linear-time solution.

What if I need to handle arrays of different sizes?

The solution still works efficiently regardless of the array sizes, as long as you use the linear scan and hash lookup approach.

What is the best way to handle larger inputs?

For larger inputs, maintaining the O(n + m) time complexity with hash lookups ensures optimal performance, as opposed to using slower methods like sorting.

#349

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。示例 1：输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2] 示例 2：输入： nums1 = [4,9,5], nu…

数组哈希表双指针二分查找排序

题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

lightbulb

解题思路

方法一：哈希表或数组

我们先用哈希表或者一个长度为 $1001$ 的数组 $s$ 记录数组 $nums1$ 中出现的元素，然后遍历数组 $nums2$ 中每个元素，如果元素 $x$ 在 $s$ 中，那么将 $x$ 加入答案，并且从 $s$ 中移除 $x$ 。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n+m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $nums1$ 和 $nums2$ 的长度。

1

2

3

4

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

speed

复杂度分析

指标	值
时间	O(n + m)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
A successful solution will efficiently scan through both arrays and utilize a hash table or set for fast lookups.
question_mark
The candidate should avoid unnecessary sorting or complex operations, focusing instead on the linear scan and hash table approach.
question_mark
Watch for the candidate using inefficient solutions that don't ensure uniqueness or have higher time complexity than O(n + m).

warning

常见陷阱

外企场景

error
Failing to remove duplicates from the result, leading to incorrect output.
error
Using an inefficient solution with a higher time complexity, such as sorting the arrays, which would make the solution O(n log n).
error
Not utilizing hash tables or sets to efficiently check for intersections and uniqueness.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays are already sorted? In this case, the two-pointer technique could be used to find intersections more efficiently.
arrow_right_alt
What if the arrays contain only unique elements? The problem becomes simpler as you only need to find the intersection without needing to handle duplicates.
arrow_right_alt
How would this solution change if the arrays were much larger? You could explore further optimizations or techniques, but the hash lookup method will still be efficient.

help

常见问题

外企场景

继续练习

#350 两个数组的交集 II #532 数组中的 k-diff 数对 #1346 检查整数及其两倍数是否存在