判断数组中是否存在重复元素
哪些公司问过
答案要点
- 哈希集合:遇到已存在即重复,时间 O(n),空间 O(n),最常用
- 排序后比较相邻元素:O(n log n),原地排序额外空间小,但改变原数组
- 暴力两两比较 O(n²),只适合很小的数组
- 数值范围有限时用计数数组、位图或原地交换,O(n) 时间 O(1) 空间
- 比较集合大小与数组长度也可判断,但不能提前返回
易错点
- 排序法没有说明会修改原数组
- 说哈希法空间是 O(1)
- 忽略数值范围有限时的更优解法
面试官常见追问
- 如果要判断距离不超过 k 的两个位置有重复呢?
- 内存不够放下哈希集合怎么办?
- 哈希集合的最坏情况是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。