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

解题思路

本题可以使用两种主要解法：

1. 哈希集合法

   • 使用HashSet存储nums1中的元素
   • 遍历nums2，查找在HashSet中存在的元素
   • 将找到的元素加入结果集合

2. 数组标记法

   • 由于数值范围已知（0-1000），可以使用数组作为哈希表
   • 使用布尔数组记录nums1中出现的数字
   • 遍历nums2，找出在nums1中出现过的数字

图解思路

哈希集合法流程分析

数组标记法状态分析

代码实现

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

性能对比

代码亮点

1. 🎯 利用集合特性自动去重
2. 💡 使用语言内置的集合操作简化代码
3. 🔍 空间换时间，提高查找效率
4. 🎨 代码结构清晰，易于理解

常见错误分析

1. 🚫 忘记处理重复元素
2. 🚫 未考虑数组为空的情况
3. 🚫 使用List导致重复元素
4. 🚫 手动实现去重降低效率

解法对比

相关题目

• LeetCode 350. 两个数组的交集 II - 中等
• LeetCode 1002. 查找共用字符 - 简单

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第349题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！