在面试题和实际业务中，经常遇到这样一类问题：一个本应包含连续数字的数组，因为某些原因丢了一个或几个数字，需要用算法把它们找回来。比如订单号序列漏发、日志分片缺失、分页数据断档等场景，本质上都是同一个模型。这类问题看似简单，但不同的解法在时间复杂度、空间占用和可读性上差别很大，用PHP实现时还有一些语言层面的细节值得注意。本文从最基础的单个缺失数字入手，逐步扩展到多个缺失、无序数组等变体，给出完整代码和性能分析。
问题定义与暴力解法的局限
先明确题目：假设一个数组本应包含从0到n的n+1个数字，实际只存了n个，恰好缺一个，且数组本身无序。例如n为4时，完整序列是0、1、2、3、4共5个数，而实际数组只有4个元素，比如[3,0,1,4]，缺失的是2。解题前必须先确认数字起点是0还是1，这直接影响公式推导。
最直观的暴力做法是双重循环：外层遍历0到n的每个候选数字，内层扫描数组判断是否存在。这种写法时间复杂度是O(n²)，当数组规模达到十万级别时，PHP脚本的执行时间会明显拉长，放在Web请求里基本不可接受。暴力解法的价值在于思路兜底和结果验证，实际生产环境应该优先考虑下面几种线性算法。
求和公式法：用数学差值直接算出答案
等差数列求和是这类问题的经典切入点。从0到n的所有数字之和可以用公式n*(n+1)/2直接算出，这个理论值减去数组实际元素之和，差值就是缺失的那个数字。整个思路只需要一次遍历累加，时间复杂度O(n)，空间复杂度O(1)，是单缺失场景的首选。
function findMissingBySum(array $nums): int
{
$n = count($nums);
// 数组长度为 n，说明完整序列是 0 到 n，共 n+1 个数
$expectedSum = $n * ($n + 1) / 2;
$actualSum = array_sum($nums);
return $expectedSum - $actualSum;
}
$nums = [3, 0, 1, 4];
echo findMissingBySum($nums); // 输出 2
这个方法依赖一个前提：数字范围从0开始且只缺失一个。如果序列从1开始，公式需要相应调整，或者干脆用range生成完整序列再求和，让代码自己适应边界。另外要注意整数溢出问题，当n非常大时，n*(n+1)/2可能超出int范围，PHP会自动转成浮点数，此时结果可能出现精度偏差，可以改用逐项做差的方式规避。
求和法还有一个变体是求积法，用完整序列阶乘除以实际阶乘来定位缺失值。但阶乘增长极快，几十个数字就会溢出成浮点数丢失精度，在PHP里实用性远不如求和法，了解思路即可，不建议实际使用。
异或法：利用位运算抵消成对元素
异或运算有一条重要性质：任何数字与自身异或结果为0，与0异或保持原值，并且满足交换律和结合律。把0到n的所有数字与数组中的所有数字放在一起连续异或，成对出现的数字会互相抵消为0，最后剩下的异或结果就是那个缺失的数字。
function findMissingByXor(array $nums): int
{
$n = count($nums);
$result = $n; // 用 n 做初始值，补上下界这个数字
for ($i = 0; $i < $n; $i++) {
$result ^= $i ^ $nums[$i];
}
return $result;
}
$nums = [9, 6, 4, 2, 3, 5, 7, 0, 1];
echo findMissingByXor($nums); // 输出 8
这段代码把下标0到n-1与对应位置的数组元素配对异或，同时用初始值n补上上界，保证0到n每个数字都参与运算一次。异或法同样做到O(n)时间和O(1)空间，而且全程不涉及加减运算，天然不存在溢出风险，这是它相对求和法的一个实际优势。缺点是原理不够直观，代码可读性稍差，团队协作时建议在函数注释里把抵消逻辑写清楚。
标记法：用哈希表处理多个缺失数字
前面两种方法都只能处理单个缺失的情况。如果数组里缺失的数字不止一个，最稳妥的思路是标记法：先根据数组长度和缺失个数推算出数字上界，建立一个布尔标记数组，遍历输入时把出现过的数字对应位置标记为true，最后收集所有仍为false的位置，就是全部缺失的数字。
function findMissingByMark(array $nums, int $missingCount): array
{
// 完整序列的数字总个数
$n = count($nums) + $missingCount;
$mark = array_fill(0, $n + 1, false);
foreach ($nums as $v) {
if ($v >= 0 && $v <= $n) {
$mark[$v] = true;
}
}
$missing = [];
foreach ($mark as $num => $exists) {
if (!$exists) {
$missing[] = $num;
}
}
return $missing;
}
$nums = [4, 3, 2, 7, 8, 2, 3, 1];
print_r(findMissingByMark($nums, 2)); // 输出 5 和 6
标记法时间复杂度O(n)，但需要额外O(n)空间存放标记数组。它的优势在于思路通用，不依赖只缺一个的假设，还能容忍数组中出现重复元素而不影响结果。PHP内置的数组本身就是有序哈希表，isset判断接近常数时间，所以标记法在PHP里实现起来非常自然，性能表现也稳定。
如果只是想快速得到结果，PHP还提供了一个极其简洁的写法：用range生成完整序列，再用array_diff做差集。这种写法代码量最少，语义一目了然，缺点是range会一次性分配整段内存，数据量大时内存峰值比标记法更高，需要结合服务器配置权衡。
function findMissingByDiff(array $nums): array
{
$n = count($nums);
// 假设序列从 1 到 n+1，缺失一个数字
$full = range(1, $n + 1);
return array_values(array_diff($full, $nums));
}
print_r(findMissingByDiff([1, 2, 4, 5])); // 输出 Array ( [0] => 3 )
性能对比与选型建议
把几种方案放在一起比较：求和法和异或法都是O(n)时间加O(1)空间，适合缺失数字个数为1的场景；标记法是O(n)时间加O(n)空间，适合任意缺失个数且可能存在重复元素的情况；range加array_diff的写法代码最短，内部同样要构建哈希表，空间开销与标记法接近，胜在开发效率。
实际选型时可以遵循几条原则：面试或纯算法场景优先写求和法，思路清晰且容易向面试官解释推导过程；担心数值溢出或数字上界极大时改用异或法；业务代码里面对无序、可能有重复、缺失个数不定的脏数据，直接用range加array_diff的组合最省心，可读性带来的维护收益往往超过那一点性能差异。
还有一个容易被忽略的细节：如果输入数组本身是有序的，问题可以进一步简化。此时只需一次线性扫描，比较相邻元素的差值，差大于1的地方就是缺失区间；甚至可以利用有序这个特征用二分查找，把时间复杂度压到O(log n)。有序与无序是两种完全不同的问题形态，动手写代码前先确认数据特征，能避免走不少弯路。