LeetCode第349题_两个数组的交集
LeetCode 第349题：两个数组的交集
📖 文章摘要
本文详细解析LeetCode第349题"两个数组的交集"，这是一道哈希表应用的经典问题。文章提供了基于哈希集合和数组的两种解法，包含C#、Python、C++三种语言实现，配有详细的思路分析和性能对比。适合正在学习哈希表和集合操作的程序员。
核心知识点： 哈希集合、数组哈希、集合操作
难度等级： 简单
推荐人群： 数据结构初学者、算法面试备考者
题目描述
给定两个数组 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
解题思路
本题可以使用两种主要解法：
-
哈希集合法
- 使用HashSet存储nums1中的元素
- 遍历nums2，查找在HashSet中存在的元素
- 将找到的元素加入结果集合
-
数组标记法
- 由于数值范围已知（0-1000），可以使用数组作为哈希表
- 使用布尔数组记录nums1中出现的数字
- 遍历nums2，找出在nums1中出现过的数字
图解思路
哈希集合法流程分析
| 步骤 | 操作 | 数据状态 | 说明 |
|---|---|---|---|
| 初始状态 | - | nums1=[1,2,2,1], nums2=[2,2] | 原始输入 |
| 第一步 | 创建HashSet | set={1,2} | 对nums1去重 |
| 第二步 | 遍历nums2 | result={2} | 找到交集元素 |
数组标记法状态分析
| 情况 | 标记数组 | 结果数组 | 说明 |
|---|---|---|---|
| 初始状态 | [0,0,0,…] | [] | 全部初始化为0 |
| 处理nums1后 | [0,1,1,0,…] | [] | 标记nums1中的数字 |
| 处理nums2后 | [0,1,1,0,…] | [2] | 收集交集元素 |
代码实现
C# 实现
public class Solution {public int[] Intersection(int[] nums1, int[] nums2) {HashSet<int> set = new HashSet<int>(nums1);HashSet<int> resultSet = new HashSet<int>();foreach (int num in nums2) {if (set.Contains(num)) {resultSet.Add(num);}}return resultSet.ToArray();}
}
Python 实现
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:return list(set(nums1) & set(nums2))
C++ 实现
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};
执行结果
C# 实现
- 执行用时：140 ms
- 内存消耗：41.8 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：15.1 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：10.2 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 140 ms | 41.8 MB | 代码简洁，但性能较差 |
| Python | 36 ms | 15.1 MB | 语法简单，性能中等 |
| C++ | 4 ms | 10.2 MB | 性能最优，内存占用小 |
代码亮点
- 🎯 利用集合特性自动去重
- 💡 使用语言内置的集合操作简化代码
- 🔍 空间换时间，提高查找效率
- 🎨 代码结构清晰，易于理解
常见错误分析
- 🚫 忘记处理重复元素
- 🚫 未考虑数组为空的情况
- 🚫 使用List导致重复元素
- 🚫 手动实现去重降低效率
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 哈希集合法 | O(n+m) | O(n) | 实现简单，通用性强 | 需要额外空间 |
| 数组标记法 | O(n+m) | O(1) | 空间复杂度低 | 受数值范围限制 |
相关题目
- LeetCode 350. 两个数组的交集 II - 中等
- LeetCode 1002. 查找共用字符 - 简单
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第349题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！