当一个包含1到n的整数数组中某个数字被替换为-1时，无需线性遍历即可在o(1)额外空间、o(n)时间复杂度内精准定位原值——核心思路是利用等差数列求和公式与实际数组和的差值进行推算。
当一个包含1到n的整数数组中某个数字被替换为-1时，无需线性遍历即可在o(1)额外空间、o(n)时间复杂度内精准定位原值——核心思路是利用等差数列求和公式与实际数组和的差值进行推算。
在标准场景中，若数组 arr 长度为 N，且本应严格包含 1 到 N 的所有正整数（无重复、无缺失），但其中恰好一个元素被篡改为 -1，则我们可通过数学方法以最优效率还原该被替换的数字。
原理简析
理想数组的理论总和为等差数列和：
[
S{\text{ideal}} = \frac{N(N+1)}{2}
]
而实际数组中，原值 x 被 -1 替代，因此实际总和为：
[
S{\text{actual}} = S{\text{ideal}} - x + (-1) = S{\text{ideal}} - x - 1
]
移项可得：
[
x = S{\text{ideal}} - S{\text{actual}} - 1
]
注意：由于 S_{\text{actual}} 包含 -1，直接计算 S_{\text{ideal}} - S_{\text{actual}} 会得到 x + 1，故最终结果需减去 1。
实现代码（Java）
int n = 1_000_000;
long idealSum = (long) n * (n + 1) / 2L;
// 示例：构造含-1的测试数组（生产环境直接使用输入数组）
List<integer> arr = IntStream.rangeClosed(1, n)
.boxed()
.collect(Collectors.toCollection(ArrayList::new));
Collections.shuffle(arr);
int replacedIndex = 132939;
int original = arr.set(replacedIndex, -1); // 记录原值用于验证
long actualSum = 0;
for (int num : arr) {
actualSum += num;
}
int found = (int) (idealSum - actualSum - 1);
System.out.println("找回的原始数字: " + found); // 输出：351316
System.out.println("验证（原始值）: " + original); // 输出：351316</integer>
关键优势与注意事项
- ✅ 时间复杂度 O(N)：仅需单次遍历求和，优于任何基于排序或哈希的方案；
- ✅ 空间复杂度 O(1)：除存储数组本身外，仅用常量级额外变量；
- ⚠️ 前提严格：必须确保数组长度为 N，且原始数据恰好是 1~N 的完整排列（无缺失、无重复、无越界值）；
- ⚠️ 数值溢出防护：N 较大时（如 ≥10⁵），
idealSum必须用long计算，避免int溢出导致结果错误； - ❌ 不适用于多个替换、替换为其他负数、或存在重复/缺失等更复杂异常场景——此时需改用位运算（如异或）或哈希集合辅助判断。
综上，该方法是以数学洞察替代暴力搜索的经典范例，在满足前提条件下，是理论最优、工程最简的解决方案。
