异或法最快最省空间，适用于0到n缺一个数的情形：初始化res为n，再将下标i与nums[i]逐个异或，最终res即缺失数；其他情况需用哈希集合或二分查找。
用异或运算找缺失数字最省事
如果数组是 0 到 n 的连续整数中恰好缺一个，且其他数字不重复、不越界，直接用异或就能在 O(n) 时间、O(1) 空间内搞定。原理是 a ^ a == 0，a ^ 0 == a，把所有下标和所有值一起异或，成对的全消掉，只剩那个没出现的数。
实操写法：
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = n; // 先异或上 n，因为下标只到 n-1
for (int i = 0; i < n; i++) {
res ^= i ^ nums[i];
}
return res;
}- 别漏掉
n：数组长度为n，完整范围是0..n（共n+1个数），所以初始值设为n - 不要先算总和再减——可能溢出，尤其用
int存大数组时 - 异或不依赖顺序，也不怕中间有负数（只要题目允许负数输入，但常规题默认非负）
当数组不是从 0 开始或范围不固定时
比如给的是 [3, 4, 5, 7]，缺 6，这时不能直接套异或。得先确认“该有哪些数”。常见做法是排序后线性扫，或用哈希集合记录已出现的数。
用 unordered_set 最直观：
立即学习“C++免费学习笔记（深入）”；
int findMissing(const vector<int>& arr) {
if (arr.empty()) return 0;
unordered_set<int> seen(arr.begin(), arr.end());
int minVal = *min_element(arr.begin(), arr.end());
int maxVal = *max_element(arr.begin(), arr.end());
for (int x = minVal; x <= maxVal; x++) {
if (seen.find(x) == seen.end()) return x;
}
// 如果没找到，说明缺的是边界外的数，按需返回 minVal-1 或 maxVal+1
return maxVal + 1;
}- 时间复杂度
O(n)，但空间要O(n) - 注意边界：缺的数可能不在
[minVal, maxVal]内，比如[1,2,3]缺0或4，得看题目定义 - 如果数组已排序，就别建 set 了，直接双指针或二分更省空间
用二分查找加速（仅限已排序且等差）
如果数组已升序排列，且本应是公差为 1 的等差序列（如 0,1,2,3,4,5），那么缺失位置必然导致“下标 ≠ 值”的第一个点。此时可用二分把时间压到 O(log n)。
关键判断逻辑：
int missingNumberSorted(const vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] != mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // 最终 left 就是缺失值（因为下标即应有值）
}- 这个解法严格依赖“原序列从 0 开始、公差为 1”，否则
nums[mid] != mid这个条件不成立 - 别忘了检查边界：若全程
nums[i] == i，说明缺的是最后一个数，即nums.size() - 实际调用前务必确认输入是否已排序，否则结果完全不可靠
容易被忽略的边界情况
很多实现在线上跑不过，往往栽在这些地方：
- 空数组：
vector<int>{}，按题意可能返回0或报错，得看约束 - 单元素数组：
[0]缺1，[1]缺0，异或写法里n == 1，初始res = 1，再异或0 ^ 0→ 结果是1，正确；但手动枚举时容易漏判 - 数据类型溢出：用
long long算总和虽稳，但不如异或干净；C++ 中size_t和int混用可能触发隐式转换警告 - 题目没说“只缺一个”，但代码假定只缺一个——遇到多个缺失，所有上述方法都会失效
最稳妥的做法，是先读清题干里关于输入范围、缺失个数、起始值的描述，再选对应解法。异或最快最安全，但适用场景最窄；set 最通用，但费内存；二分最快但限制最多。
