268. 缺失数字（Missing Number）

频次 ★★★ · 难度 🟢 · 高频：字节/腾讯

题目

给定一个包含 [0, n] 中 n 个数的数组 nums，找出缺失的那个数。

示例：

输入: nums = [3, 0, 1]
输出: 2

输入: nums = [0, 1]
输出: 2

输入: nums = [9,6,4,2,3,5,7,0,1]
输出: 8

思路

位运算法（异或）：利用异或 a ^ a = 0 和 a ^ 0 = a 的性质，将 [0, n] 的 n+1 个数与数组中的 n 个数全部异或一遍，成对出现的都消为 0，剩下的就是缺失的数。

也可以用数学法：0 + 1 + ... + n = n(n+1)/2，减去数组所有元素的和，差值即为缺失的数。注意整数溢出。

代码

public int missingNumber(int[] nums) {
    int xor = 0;
    for (int i = 0; i <= nums.length; i++) {
        xor ^= i;
    }
    for (int num : nums) {
        xor ^= num;
    }
    return xor;
}

简化版（一次遍历）：

public int missingNumber(int[] nums) {
    int xor = nums.length;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

复杂度

• 时间：O(n)
• 空间：O(1)

边界条件

• 缺失的是 0：异或法会得到 0，数学法也能正确算出。
• 缺失的是 n（最大值）：异或法无影响；数学法注意 n(n+1)/2 可能溢出，但题目约束通常不超 int 范围。
• 数组中只有一个元素也不影响。

变式

• 缺失一个数但数组可能为空：如果 nums 是空数组，说明 n=0，缺失的是 0。
• 缺失多个数（448. 找到所有数组中消失的数字）：无法用异或，用原地哈希。
• 找出重复的数 + 缺失的数：见 645. Set Mismatch。
• 只出现一次的数字（136. 只出现一次的数字）：同是异或消消乐。

易错点

• 循环范围容易写错：[0, n] 有 n+1 个数，但数组只有 n 个数，异或时注意上限是 nums.length 而不是 nums.length - 1。
• 数学法求和可能溢出：虽然题目给的 n 在 int 范围内，但 n(n+1)/2 可能在 n 接近 2^31-1 时溢出。用 long 或异或法避免。

面试追问

• 数学法和异或法各有什么优劣？ 数学法更直观，但求和有溢出风险（需用 long 或分步运算避免）；异或法无溢出问题且代码简洁，面试推荐异或法。
• 如果数组是排序的，有没有更快的办法？ 排序后可以用二分查找 O(log n)，通过比较 nums[i] 和 i 是否相等找到第一个缺失的位置。

关联题

• 同套路：136. 只出现一次的数字 —— 异或消消乐
• 进阶：448. 找到所有数组中消失的数字（原地哈希找多个缺失）
• 易混：287. 寻找重复数（用值做下标找环）
• 知识点：位运算异或性质见位运算