LeetCode 268. 丢失的数字

◎

本节目标

用下标和值域的异或配对，在常数额外空间内找出缺失数字。

这道题承接二进制与位运算基础。数组本应包含 0 到 n 的所有数字，却恰好少了一个；可以让完整值域和现有数组在异或中两两消去。

查看原题

题意与约束

给定长度为 n 的数组 nums，其中的元素互不相同，且每个元素都属于 0 到 n。恰好有一个数字没有出现在数组中，返回它。

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• nums 中所有元素互不相同。

把完整集合与现有集合配对

完整集合是 0, 1, ..., n，数组提供的是其中除答案外的 n 个值。异或满足交换律和结合律，也满足 x ^ x = 0，因此把两组数全部异或后，每个已出现的数都会恰好配成一对，只有缺失值留下。

无需再单独遍历 0 到 n：数组下标正好给出 0 到 n - 1。循环中同时异或下标 i 和数组值 nums[i]，即可完成两组的配对。

为什么先放入 n

下标只能覆盖 0 到 n - 1，完整集合还多一个 n。所以先令 answer = n，再从数组长度中取得其余完整集合成员。

这也是边界最容易遗漏的地方：若答案恰好是 n，它不在任何数组下标中，只有初始化时放入才能保留下来。

异或消去过程

以 nums = [3, 0, 1] 为例，n = 3，完整集合为 0, 1, 2, 3：

answer = 3 ^ (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1)
       = (3 ^ 3) ^ (0 ^ 0) ^ (1 ^ 1) ^ 2
       = 2

顺序并不影响结果；上式只是把相同值重新排在一起，以便看清哪些项消去。

代码实现

两份源码都先把 n 放入 answer，再在一次循环中异或下标和值，不使用求和或额外容器。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int answer = static_cast<int>(nums.size());
        for (int i = 0; i < static_cast<int>(nums.size()); i++) {
            answer ^= i ^ nums[i];
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        answer = len(nums)
        for i, num in enumerate(nums):
            answer ^= i ^ num
        return answer

复杂度分析

• 时间复杂度：遍历数组一次，为 O(n)。
• 额外空间复杂度：只维护 answer，为 O(1)。

易错点

• 忘记先异或 n：下标只到 n - 1，答案为 n 时会计算错误。
• 把 i 当成数组值：循环中必须同时异或 i 和 nums[i]，它们分别代表完整集合和现有集合。
• 改用等差数列求和却忽略范围：n * (n + 1) / 2 - sum(nums) 也可求解，但在固定宽度整数语言中乘积或累计和可能溢出；异或没有这类算术溢出风险。
• 用集合补齐：集合能通过，但会额外使用 O(n) 空间，未利用下标和值域一一对应的结构。

模式迁移

遇到“数组包含一个连续值域中的所有数，恰少一个”的题，先检查下标能否覆盖该值域的大部分，再把无法由下标覆盖的边界值预先放入累计量。这道题是二进制与位运算基础中的“下标配对”模式：只要两组元素除少数项外能一一对应，就可以考虑异或消去，而不必依赖可能溢出的算术求和。