043 · Intersection of Two Arrays II

algorithm

Published

June 23, 2026

My First Thoughts

嗯，这里需要取交集，如果是在 R 里，直接用类似 intersect(a, b) 的函数就行了。Python 大概率也有类似的模块或者写法。

但这里考的是算法，所以不能只想着直接调用现成函数，而是要考虑底层怎么实现。

题目的输入是 nums1 和 nums2 两个 list，返回的也是 list。

一个自然的问题是：到底应该循环哪一个数组？

如果先看长度，循环短的那个好像更加节省时间：

if len(nums1) < len(nums2):
    ...

但可能也存在问题。循环短的数组虽然循环次数少，但每次查找可能要去另一个更长的数组里找，整体是否更优不一定。

然后看题目说“交集里的每个元素可以重复出现”。这和前一道 Intersection of Two Arrays 不一样。

如果可以重复，显然就不能直接用 set 了。set 会把重复数字都压成一个：

set([2, 2, 2])  # {2}

那还有什么其他方法吗？

仔细想过可能还是就是遍历list了：

share_nums = []

for num in nums1:
    if num in nums2:
        share_nums.append(num)

return share_nums

这个写法抓住了一个基本方向：如果 num 在另一个数组里也出现了，它就应该是交集的一部分。

Why That Is Not Enough

上面的方向接近了，但有一个具体问题：它忘记移除已经匹配过的 nums2 中的数值了。

看这个例子：

nums1 = [2, 2, 2]
nums2 = [2]

如果用刚才的代码：

share_nums = []

for num in nums1:
    if num in nums2:
        share_nums.append(num)

return share_nums

每次循环到 2，都会发现：

2 in nums2

是 True。

所以它会返回：

[2, 2, 2]

但正确答案应该是：

[2]

因为 nums2 里只有一个 2，它只能和 nums1 里的一个 2 配对。配对以后，这个 2 就不能再被后面的 2 重复使用。

所以真正缺少的不是“能不能判断存在”，而是：

匹配成功以后，要减少这个数字可匹配的次数。

一种朴素修正是：如果 num in nums2，就把它从 nums2 里删掉一个。

比如：

share_nums = []

for num in nums1:
    if num in nums2:
        share_nums.append(num)
        nums2.remove(num)

return share_nums

这个版本在逻辑上已经能处理重复次数。因为每找到一次，就从 nums2 中移除一个对应数字。

但它还有一个效率问题。num in nums2 在 list 里查找，可能要从头扫到尾；nums2.remove(num) 也要找并移动元素。也就是说，我们反复在 list 里做线性查找和删除。

所以这里可以把 nums2 从 list 转成一个计数字典，也就是 frequency table。这个结构之前已经用过很多次：key 是数字，value 是这个数字出现的次数。

Final Idea

从原来的写法出发：

for num in nums1:
    if num in nums2:
        share_nums.append(num)

核心逻辑还是不变：遍历一个数组，看当前数字能不能在另一个数组中匹配。

需要改变的是 nums2 的表示方式。原来直接在 list 里查：

num in nums2

这对“是否存在”够用，但对这题的重复元素不够清晰。更合适的是先把 nums2 转成计数字典：

counts = {}

for num in nums2:
    counts[num] = counts.get(num, 0) + 1

这样 counts[num] 就是 num 在 nums2 中的频次。

然后遍历 nums1：

for num in nums1:
    if counts.get(num, 0) > 0:
        share_nums.append(num)
        counts[num] -= 1

这里的 counts[num] -= 1 就对应前面朴素做法里的 nums2.remove(num)。区别是：我们不再真的修改 list，而是在计数字典里把频次减一。

如果题目像 039 那样不要求重复，set 会更直接：只记录“出现过没有”就够了。计数字典也能做，但会多保存一份次数信息，语义和常数开销都更重。

这题要求保留重复元素，所以计数字典正好匹配问题。

Why It Works

counts 记录的是 nums2 中每个数字的可用频次。

遍历 nums1 时，对于每个 num：

如果 counts.get(num, 0) == 0，说明 nums2 中没有这个数字，或者对应频次已经被前面的匹配用完了，所以不能加入答案
如果 counts.get(num, 0) > 0，说明它在两个数组中都有一个可用位置，所以把它加入 share_nums

加入答案以后，要执行：

counts[num] -= 1

这一步保证同一个 nums2 中的出现次数不会被重复使用。

因此，某个数字最终加入答案的次数，不会超过它在 nums1 中出现的次数，也不会超过它在 nums2 中出现的次数。正好符合题目对交集重复元素的要求。

Code

def intersect(nums1, nums2):
    counts = {}

    for num in nums2:
        counts[num] = counts.get(num, 0) + 1

    share_nums = []

    for num in nums1:
        if counts.get(num, 0) > 0:
            share_nums.append(num)
            counts[num] -= 1

    return share_nums

如果想稍微优化空间，可以用较短的数组建 counts：

def intersect(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    counts = {}

    for num in nums1:
        counts[num] = counts.get(num, 0) + 1

    share_nums = []

    for num in nums2:
        if counts.get(num, 0) > 0:
            share_nums.append(num)
            counts[num] -= 1

    return share_nums

第二版里，counts 用较短的数组建立，所以额外空间会更小一些。核心仍然是同一件事：每匹配一次，就把频次减一。

Complexity

Time	\(O(n + m)\) - `n` 是 `nums1` 的长度，`m` 是 `nums2` 的长度；一个数组用来建次数表，另一个数组用来查找和消耗次数
Space	\(O(k)\) - `k` 是用来建表的数组中不同数字的数量；如果用较短数组建表，最多是 \(O(\min(n, m))\)

Takeaway

set 适合只关心“是否出现过”的交集；计数字典适合关心“出现了几次”的交集。题目一旦要求保留重复元素，就要从存在性判断升级到频次记录。

← Quiz