找到所有数组中消失的数字

问题拆解

数组长度为 n，每个元素都落在 [1, n]，可能有重复。要找出 [1, n] 里没在数组中出现过的所有数字。进阶要求不使用额外空间、时间 O(n)。

用一个哈希集合记录出现过的数字，再遍历 1..n 查缺，逻辑很直接，但要额外的 O(n) 空间。关键的观察是：数值范围 [1, n] 和下标范围 [0, n-1] 一一对应，数字 v 天然可以映射到下标 v - 1。既然这样，就不必再借外部容器——数组自己就是一张现成的哈希表。

用下标充当哈希桶，把“某个数出现过”的信息编码进那个位置元素的正负号里。

原地哈希：标负法

第一遍遍历：对每个值 v，找到它对应的下标 abs(v) - 1，把那个位置的元素改成负数，表示“v 来过”。第二遍遍历：仍然是正数的下标，说明对应的数字从没被标记过，也就是缺失的数字。

def findDisappearedNumbers(nums):
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]
    return [i + 1 for i, x in enumerate(nums) if x > 0]

有两个细节要留意。取下标时必须用 abs(x)，因为 x 可能在更早的步骤里已经被标成了负数，它代表的原始数值仍是 abs(x)。判断 nums[idx] > 0 再取反，是为了让重复出现的数字不会把负号又翻回正号。

第二遍里，下标 i 处仍为正，意味着从没有哪个元素映射到 i，于是 i + 1 就是一个缺失的数。整个过程只在原数组上翻转符号，没有申请新空间。

复杂度

指标	复杂度	原因
时间	O(n)	两次线性遍历
空间	O(1)	复用原数组，返回值不计入

可以迁移的模式

• 数值范围和下标范围能对上，可以拿下标当哈希键；
• 允许临时“污染”原数组（改符号、加偏移），事后还能还原本值；
• 想把计数或存在性判断的空间压到常数。

同样的原地哈希思路，也能解“找重复数字”“缺失的第一个正数”这类值域受限的题。