企业官网建设流程全解析

LeetCode 349. Intersection of Two Arrays 题解：哈希表空间换时间求两个数组的交集

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇题解以当前仓库中 problems/349.intersection-of-two-arrays.en.md（及其中文版 problems/349.intersection-of-two-arrays.md）为核心骨架，完整继承题目定义、解题思路、双语言代码与复杂度分析，并结合仓库中关于"空间换时间"算法思想的论述进行源码级扩充。读完本文，你将掌握用哈希表在 O(N) 时间内求两数组去重交集的完整套路，并能直接迁移到其他"去重 + 快速查找"类问题。

题目背景与问题定义

LeetCode 第 349 题 "Intersection of Two Arrays"（两个数组的交集）是一道典型的哈希表入门题，被仓库的 README.md 收录在简单难度题单中，同时出现在 collections/easy.md 的经典简单题合集里。

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]

说明（题目的两个关键约束）：

• 输出结果中的每个元素一定是唯一的（即结果需要去重）；
• 可以不考虑输出结果的顺序（因此返回[9,4]或[4,9]均为正确答案）。

从示例 1 可以看出，nums1和nums2中都含有重复元素（2出现了两次），但输出只保留一个2；示例 2 中9、4在两个数组中均多次出现，输出同样各保留一个。理解"结果去重"这一约束，是设计正确解法的前提。

前置知识：哈希表与"空间换时间"

本题解要求的前置知识只有一个：哈希表（hashtable）。

哈希表以O(1)的平均时间复杂度完成"键是否存在"的判定与读写。这一点在仓库的 thinkings/README.md 中有明确呼应——该文件将"空间换时间"列为暴力优化法的核心手段，并明确指出其典型载体包括哈希表、前缀树等：

暴力优化法也是必须掌握的……有剪枝，空间换时间等。其中空间换时间又有很多，比如哈希表，前缀树等等。

本仓库中的多道题解都运用了这一思想，例如 problems/1.two-sum.md（两数之和）与 problems/560.subarray-sum-equals-k.md（和为 K 的子数组）均通过哈希表把暴力枚举的二次复杂度降为线性。理解 349 题，等于掌握了这批哈希表题目的最小可运行范本。

解题思路：两轮遍历 + 哈希表标记

原文档给出的核心思路非常精炼，分三步：

1. 建表：先遍历第一个数组nums1，把每个元素作为键写入哈希表（同时把元素本身作为值，见下文"误区"分析）；
2. 查表：再遍历第二个数组nums2，如果当前元素在哈希表中存在，说明它是交集成员，push进结果数组；
3. 清空标记：命中后立即把该键从哈希表中"清空"（置为undefined或pop删除），避免nums2中的重复元素被再次计入，从而天然满足"结果唯一"的约束。

最后返回结果数组即可。

为什么需要"清空"这一步？因为nums2中可能有重复元素（如示例 1 的[2,2]）。若不清空，第二次遇到2时哈希表中仍然存在2，会再次push，导致输出[2,2]，违反"结果唯一"的约束。清空标记使"每个元素在结果中最多出现一次"这一约束在遍历过程中自动被满足，无需额外的去重集合。

为什么先遍历nums1而不是nums2？二者在算法上对称，选择哪个数组建表都可以。原文档选择先遍历第一个数组建表、再遍历第二个数组查表，实现上没有任何区别，最终时间复杂度相同。

关键点解析

• 空间换时间：用一块哈希表的额外空间，把"判断一个元素是否在另一数组中出现"的代价从每次 O(N) 的线性扫描降为 O(1)，从而让整体时间复杂度从暴力的 O(N²) 降到 O(N)。这正是 thinkings/README.md 所总结的优化思路在本体的具体化。

多语言实现

原文档声明代码支持JS、Python两种语言，以下代码完整继承自原文档（JS 代码中的笔误空格已修正为标准语法，可直接运行）。

Javascript 实现（哈希表 + 双轮遍历）

/** * @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 实现一（哈希表 + 双轮遍历）

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 实现二（集合运算一行解）

原文档同时给出利用 Python 内置集合的极简解法，一行完成"去重 + 求交集"：

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

set()天然去重，&运算符对两个集合求交集，语义与题目"输出唯一元素、不考虑顺序"的约束完全吻合，是最贴近 Python 语言习惯的写法。它同样基于哈希表的 O(1) 查找能力，只是把"手动建表 + 手动去重"的细节交由语言内置实现完成。

复杂度分析

设nums1的长度为 N、nums2的长度为 M，则：

• 时间复杂度：O(N + M)。两轮遍历各执行一次，每个元素只被处理一次；哈希表的读写均为 O(1)。原文档简记为 O(N)。
• 空间复杂度：O(N)。visited哈希表的大小取决于nums1去重后的元素个数，最坏情况下为 O(N)；结果数组ret不计入辅助空间（或最多 O(min(N,M))）。

相比之下，朴素的暴力解法（对nums2的每个元素线性扫描nums1）时间复杂度为 O(N·M)，且还需要额外的去重处理。哈希表解法以 O(N) 的额外空间换取了一个数量级的时间收益。

边界情况与常见误区

1. 空数组：若任一输入为空，建表或查表循环不执行，最终返回[]，算法天然正确，无需特判。
2. JS 实现中为什么存visited[num] = num而不是visited[num] = true？这属于防御性写法：JS 中对象键被存储为字符串，但visited[0]访问时会自动完成类型转换，因此数字0也能正确命中。若存布尔值，需注意不要用if (visited[num])这类真值判断——当num对应的键不存在但visited[num]恰好为undefined时无碍，但任何"真值性"判断（而非!== undefined）都可能误伤边界值。原文档统一使用visited[num] = num存元素本身、用visited[num] = undefined清空，配合!== undefined判断，逻辑最为稳妥。
3. 为什么 Python 用pop而不是重新赋值？if num in visited判断的是键是否存在，Python 版用visited.pop(num)直接删除键，语义上比"置空"更彻底，也避免键残留。

思路拓展：从本题延伸到同类问题

本题是哈希表"去重交集"的入门题，掌握后可以继续向两个方向延伸：

• 保留重复元素的进阶版本：若题目改为"输出结果中每个元素出现的次数，应与该元素在两个数组中出现的次数一致"（即 Intersection of Two Arrays II 的设定），则无法用"命中即删"的简单标记，需要改为计数思路——建表时记录nums1中每个元素的出现次数，查表命中后计数减一，减到零才删除，从而保留重复元素。这一思路与仓库中 [problems/350] 同类题目相比，核心差异仅在于"键的取值是布尔标记还是计数器"。
• 排序 + 双指针：若数组本身有序（参见仓库 problems/167.two-sum-ii-input-array-is-sorted.md 的双指针范式），可先对两数组排序，再用双指针同步推进：元素相等则记录并同时前进、较小者单独前进，达到 O(N log N) 时间、O(1) 额外空间的解法。这是"空间换时间"的另一面——用排序的时间代价换掉哈希表的空间。

仓库索引与配套资源

• 本题英文题解原文：problems/349.intersection-of-two-arrays.en.md
• 本题中文题解原文：problems/349.intersection-of-two-arrays.md
• 简单难度题目合集（含本题定位）：collections/easy.md
• 仓库主 README 简单题单：README.md
• "空间换时间"算法思想论述：thinkings/README.md

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode