两个千万级int数组求交集
哪些公司问过
答案要点
- 较小数组建哈希集合,遍历另一个数组查找,O(m+n)
- 命中后删除或标记,避免重复输出
- 值域 2^32 的位图需 512MB,无冲突且严格线性
- 有序时双指针 O(m+n)、空间 O(1);无序可排序后双指针
- 先确认重复元素是去重还是按出现次数保留
易错点
- 对两个数组都建哈希表,浪费内存
- 没处理重复元素,输出重复结果
- 不评估数据规模就直接说用分治外排
面试官常见追问
- 如果要保留重复次数呢?
- 如果两个数组大小相差悬殊呢?
- 内存放不下怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。