寻找替换的数字：O(N) 时间复杂度，O(1) 空间复杂度

题目描述：

有 N 个不同的数，分别是 1 到 N，在随机打乱顺序的过程中，出现了一点小误差，其中一个数换成了另一个数。请你找出谁替换了谁，要求时间复杂度是 O(N)，辅助空间 O(1)，这意味不能使用数组、map、set、vector 等。

输入：

N 个数 ai（1<=ai<=N），其中缺了一个，而又有一个数出现了 2 次，其它都出现了 1 次，数之间有一个空格。（N<2000）

输出：

两个整数 a 和 b(a 是缺的哪一个，b 是出现两次的那一个），中间有一个空格，没有回车

输入样例：

2 3 4 1 3 6

输出样例：

5 3

解题思路：

题目中限定了空间复杂度为 O(1)，这就意味着不能使用辅助空间，也就是不能使用数组、map、set、vector 等。那么我们需要从算法上入手。

我们可以先计算出 1 到 N 的和，然后遍历数组，累加数组中所有数的和，用前者减去后者得到缺失的那个数，然后将数组中所有的数相加，再减去缺失的那个数，得到数组中实际的和。将实际和减去 1 到 N 的和，得到被替换的那个数。但是这种方法有一个问题，就是如果被替换的那个数恰好是 1，那么计算 1 到 N 的和的过程中会出现溢出的问题，因此需要特判一下。

**代码：**c#include <stdio.h>

int main() { int n, i, sum1 = 0, sum2 = 0, a, b; scanf('%d', &n); for (i = 1; i <= n; i++) { sum1 += i; } for (i = 0; i < n - 1; i++) { int x; scanf('%d', &x); sum2 += x; } a = sum1 - sum2; sum2 += a; b = sum2 - sum1; printf('%d %d', a, b); return 0;