缺失数字：标记数组解法

核心结论#

输入包含 [0, n] 中的 n 个不同数字。建立长度为 n + 1 的标记数组，记录每个数字是否出现，再返回唯一未标记的位置即可。

问题#

例如 [3, 0, 1] 缺少 2，[9, 6, 4, 2, 3, 5, 7, 0, 1] 缺少 8。

核心机制#

数组索引正好覆盖完整候选范围 [0, n]。遍历输入时把 seen[value] 设为 true；第二次遍历索引时，第一个 false 就是答案。

Java 实现#

class Solution {
    public int missingNumber(int[] nums) {
        boolean[] seen = new boolean[nums.length + 1];

        for (int value : nums) {
            seen[value] = true;
        }

        for (int value = 0; value < seen.length; value++) {
            if (!seen[value]) {
                return value;
            }
        }

        throw new IllegalStateException("input does not satisfy the constraints");
    }
}

设计取舍#

标记数组直观且不修改输入，时间复杂度为 O(n)，空间复杂度为 O(n)。如果必须使用 O(1) 额外空间，可以对 [0, n] 与输入元素执行异或，或计算等差数列总和后减去输入总和；求和方案需要注意整数溢出。

验证#

覆盖缺少 0、缺少 n、仅含一个元素以及一般顺序被打乱的输入。

参考#

• LeetCode 268：丢失的数字