异或法最快最省空间，适用于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 <ul>
<li>别漏掉 <code>n</code>：数组长度为 <code>n</code>，完整范围是 <code>0..n</code>（共 <code>n+1</code> 个数），所以初始值设为 <code>n</code>
</li>
<li>不要先算总和再减——可能溢出，尤其用 <code>int</code> 存大数组时</li>
<li>异或不依赖顺序，也不怕中间有负数（只要题目允许负数输入，但常规题默认非负）</li>
</ul>
<h3>当数组不是从 0 开始或范围不固定时</h3>
<p>比如给的是 <code>[3, 4, 5, 7]</code>，缺 <code>6</code>，这时不能直接套异或。得先确认“该有哪些数”。常见做法是排序后线性扫，或用哈希集合记录已出现的数。</p>
<p>用 <code>unordered_set</code> 最直观：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
</div>
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<pre class="brush:php;toolbar:false;">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 <ul>
<li>时间复杂度 <code>O(n)</code>，但空间要 <code>O(n)</code>
</li>
<li>注意边界：缺的数可能不在 <code>[minVal, maxVal]</code> 内，比如 <code>[1,2,3]</code> 缺 <code>0</code> 或 <code>4</code>，得看题目定义</li>
<li>如果数组已排序，就别建 set 了，直接双指针或二分更省空间</li>
</ul>
<h3>用二分查找加速（仅限已排序且等差）</h3>
<p>如果数组已升序排列，且本应是公差为 1 的等差序列（如 <code>0,1,2,3,4,5</code>），那么缺失位置必然导致“下标 ≠ 值”的第一个点。此时可用二分把时间压到 <code>O(log n)</code>。</p>
<p>关键判断逻辑：</p>
<pre class="brush:php;toolbar:false;">int missingNumberSorted(const vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left <ul>
<li>这个解法严格依赖“原序列从 0 开始、公差为 1”，否则 <code>nums[mid] != mid</code> 这个条件不成立</li>
<li>别忘了检查边界：若全程 <code>nums[i] == i</code>，说明缺的是最后一个数，即 <code>nums.size()</code>
</li>
<li>实际调用前务必确认输入是否已排序，否则结果完全不可靠</li>
</ul>
<h3>容易被忽略的边界情况</h3>
<p>很多实现在线上跑不过，往往栽在这些地方：</p>
<ul>
<li>空数组：<code>vector<int>{}</int></code>，按题意可能返回 <code>0</code> 或报错，得看约束</li>
<li>单元素数组：<code>[0]</code> 缺 <code>1</code>，<code>[1]</code> 缺 <code>0</code>，异或写法里 <code>n == 1</code>，初始 <code>res = 1</code>，再异或 <code>0 ^ 0</code> → 结果是 <code>1</code>，正确；但手动枚举时容易漏判</li>
<li>数据类型溢出：用 <code>long long</code> 算总和虽稳，但不如异或干净；C++ 中 <code>size_t</code> 和 <code>int</code> 混用可能触发隐式转换警告</li>
<li>题目没说“只缺一个”，但代码假定只缺一个——遇到多个缺失，所有上述方法都会失效</li>
</ul>
<p>最稳妥的做法，是先读清题干里关于输入范围、缺失个数、起始值的描述，再选对应解法。异或最快最安全，但适用场景最窄；set 最通用，但费内存；二分最快但限制最多。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
