100张卡片拿走两张,找出被拿走的数
哪些公司问过
蚂蚁数字科技1
答案要点
- 不重复时用1000位的位图记录,剩余98张清位后仍为1的两位即被拿走的数
- 可能重复时改用计数数组,记录加1、剩余减1,计数大于0即被拿走
- 和与平方和法:a+b=s,a²+b²=q,由(a-b)²=2q-s²解出两数,额外空间O(1)
- 时间O(n)加一次值域扫描;和与平方和的量级在int范围内
易错点
- 没确认数字是否可能重复就直接用位图
- 和与平方和法推错公式,例如把(a-b)²写成q-s²
- 以为只用总和就能确定两个数,实际还需要第二个方程
面试官常见追问
- 如果只拿走一张,最简单的方法是什么?
- 用异或怎么找出两个数?
- 如果拿走k张呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。