题目

思路

一句话：从“全集的值”里减掉“数组里已经有的值”，剩下的就是缺失值；这个“减”既可以是算术减法，也可以是异或。

先说最直白的：把 0,1,...,n 每个数都去数组里问一遍“在不在”。查每个数要 O(n)，共 n+1 个数，总时间 O(n²)——能过但太慢，丢了“线性时间”的进阶要求。

稍好一点的是排序：排完后从左到右找第一个“下标与值对不上”的位置，也行，但排序要 O(n log n)，仍不够。

关键观察：这不是“大海捞针”，而是已知全集、只少一个。全集 [0,n] 的和、异或都可以直接算出来；用“全集的总量”去抵消“数组里已经出现的部分”，剩下来的自然就是缺失的那个。

两条路都满足 O(n) 时间、O(1) 空间：

• 求和作差：期望和 n(n+1)/2 减实际和。简单，但在某些语言里求和可能溢出，需要留意类型。
• 异或作差：把 0..n 和 nums 全部异或起来。因为 x ^ x = 0、x ^ 0 = x，每个出现的数都会成对抵消，只有丢失的数出现一次而留下。无溢出，且是本题所属“位运算”板块的标准写法。

选异或。

解法

先把全集 [0,n] 的每一项各“放进”答案一次：n 由初值 ans = n 表示，0..n-1 由循环下标 i 表示；随后再把数组里的每个 nums[i] 异或进来。两遍合起来，凡出现的数出现 2 次（抵消），缺失的数只出现 1 次（留下）。

以 nums = [4,2,0,1]、n = 4、缺失 3