如何找出数组中缺失的数字或重复的数字？

简化版

关键看数组的「值域」有没有规律。若是 [0, n] 里缺一个数，可用求和公式（应有和减实际和）或异或一次解决，O(1) 空间。若值域是 [1, n] 且元素可当下标，用原地哈希（把值 v 交换到下标 v 的位置，或给下标 v 处的数打负号标记）能同时找出重复和缺失，不用额外空间。

详细版

分几种经典场景：

① [0, n] 中缺 1 个（共 n 个数）：

求和法：缺失 = n(n+1)/2 − 实际总和。简单，但大数组求和可能溢出（用 long）。
异或法：把 0..n 全部异或，再异或数组所有元素，剩下的就是缺失值。不会溢出。

int missing(int[] a) {          // a 含 [0,n] 中的 n 个数
    int x = a.length;           // 先异或上 n
    for (int i = 0; i < a.length; i++) x ^= i ^ a[i];
    return x;                   // 相同的都抵消，剩缺失的
}

② [1, n] 中有 1 个重复（找重复）：

原地哈希（打标记）：遍历，对每个值 v，把下标 |v|-1 处的数取负；若发现那个位置已经是负的，说明 |v| 出现过第二次，就是重复值。

③ [1, n] 中一个数被替换成了另一个（既有重复又有缺失）：

交换归位：把每个值 v 换到它「该在」的下标 v-1 处；最后扫一遍，nums[i] != i+1 的位置就暴露了重复和缺失。

完整版教学

一、先问「值域」——这是解题钥匙

这类题的突破口永远是元素的取值范围和数量关系。因为「n 个数落在 [1,n] 或 [0,n]」意味着「值」和「下标」几乎一一对应，这个对应关系就是免费的哈希表——不用真开 HashMap，用下标本身当哈希桶。没有这个值域约束，就只能老实用哈希集合（O(n) 空间）或排序（O(n log n)）。

二、求和法与异或法（找单个缺失）

对 [0,n] 缺一个数：

求和法：完整的 0+1+…+n = n(n+1)/2，减去实际数组的和，差就是缺的那个。直观，但注意 n 大时和会溢出，用 long。
异或法：利用 x ^ x = 0、x ^ 0 = x。把 0..n 和数组元素全部异或在一起，成对出现的都两两抵消，只剩那个「只出现一次」的缺失值。异或法不会溢出，更稳。

三、原地哈希之「打负号标记」（找重复）

值域是 [1, n] 时，下标 0..n-1 正好能对应值 1..n。遍历数组，对当前值 v：

看下标 |v|-1 处的数：如果是正的，说明 |v| 第一次出现，把它取负做标记；
如果已经是负的，说明 |v| 之前来过，它就是重复值。

用「正负号」把「这个值出现过没有」的信息藏在数组自身里，省掉了额外的布尔数组。注意取绝对值，因为元素可能已被标记成负数。

四、原地哈希之「交换归位」（同时找重复和缺失）

更通用的做法是让「每个值回到它应在的位置」：值 v 应该待在下标 v-1。遍历时不断交换，直到当前位置放的是「正确的值」或遇到重复：

for (int i = 0; i < n; i++) {
    while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
        int t = nums[nums[i] - 1];       // 把 nums[i] 换到它该去的坑
        nums[nums[i] - 1] = nums[i];
        nums[i] = t;
    }
}
// 归位后扫一遍：nums[i] != i+1 的位置，nums[i] 是重复值，i+1 是缺失值
for (int i = 0; i < n; i++)
    if (nums[i] != i + 1) return new int[]{nums[i], i + 1};

归位后，凡是「下标 i 处不是 i+1」的地方，就同时暴露了那个多出来的重复值和那个空缺的缺失值。

五、方法怎么选

只找一个缺失、值域 [0,n] → 异或法（不溢出）或求和法。
只找一个重复、不能改数组 → 可用**快慢指针（Floyd 判环）**把数组当链表找环入口（值指向下标）。
既找重复又找缺失、允许改数组 → 原地哈希（交换归位或打标记）。

核心都是一句话：利用「值域 = 下标域」把数组自己当哈希表，从而做到 O(1) 额外空间。

条件	推荐方法	时间	额外空间
数字在 `1..n`，允许修改数组	负号标记 / 原地交换	O(n)	O(1)
只缺一个数且不允许修改	求和或 XOR	O(n)	O(1)
可能有多个缺失和重复	负号标记或原地哈希	O(n)	O(1)
值域不连续或包含任意整数	哈希表	O(n)	O(n)

以 [4,3,2,7,8,2,3,1] 找 1..8 中缺失数字为例，用负号标记时，看到值 4 就把下标 3 处取负，看到值 3 就把下标 2 处取负。遍历结束后，仍为正的位置对应没被访问过的数字，因此下标 4、5 为正，缺失数字是 5、6。

这类题先问清楚四件事：值域是不是 1..n，是否允许修改原数组，缺失/重复是一个还是多个，是否要求 O(1) 额外空间。

六、常见误区与追问

误区：所有缺失重复题都能用求和公式。 求和适合简单场景；多个缺失、多个重复或整数溢出风险时不稳。
误区：XOR 能直接解决多个重复。 XOR 擅长成对抵消，多个异常值混在一起时需要额外分组条件，不是通用答案。
误区：原地标记不会破坏数组。 负号标记和交换归位都会修改原数组；如果题目要求保留原数组，要先说明限制。
追问：为什么值域 1..n 很关键？ 因为可以把值 x 映射到下标 x-1，实现原地哈希。
追问：负号标记遇到重复值怎么处理？ 第二次访问同一个下标时发现已经为负，就说明该数字重复出现过。
追问：如果数组元素可能为 0 或负数怎么办？ 原地映射条件被破坏，通常改用哈希表，或先做值域转换但要保证不引入歧义。

七、加强记忆

找数组的缺失/重复，先看值域：[0,n] 缺一个用异或（不溢出）或求和公式；[1,n] 找重复用原地哈希——「打负号标记」或「交换归位」，把值当下标、用数组自身当哈希表，O(1) 空间。既找重复又找缺失就交换归位后扫一遍。不能改数组找重复可用 Floyd 判环。

简化版

详细版