找缺失的数字(LeetCode 268)及相似题
答案要点
- 求和法:n(n+1)/2 减去数组和,注意整型溢出,可边遍历边累加 i-nums[i]
- 异或法:下标、n 与所有元素一起异或,相同的数抵消,剩下的即缺失值
- 两种方法都是 O(n) 时间、O(1) 空间;排序 O(n log n),哈希 O(n) 空间
- 边界:缺失的可能是 0 或 n,求和与异或都能自然覆盖
- 相似题:287 快慢指针或值域二分,41 原地交换归位,448 原地取负标记
易错点
- 求和法直接用 int 计算 n(n+1)/2 在 n 很大时可能溢出
- 异或时漏掉数字 n 本身,导致缺失值为 n 时出错
- 把 41 题的原地交换写成 if 而不是 while,导致部分数没有归位
面试官常见追问
- 287 寻找重复数怎么做到不改数组、O(1) 空间?
- 41 缺失的第一个正数怎么做?
- 如果数组是有序的呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。