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

问题拆解

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

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

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

原地哈希：标负法

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

public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int x : nums) {
        int idx = Math.abs(x) - 1;
        if (nums[idx] > 0) {
            nums[idx] = -nums[idx];
        }
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.add(i + 1);
        }
    }
    return result;
}

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]

func findDisappearedNumbers(nums []int) []int {
    for _, x := range nums {
        idx := abs(x) - 1
        if nums[idx] > 0 {
            nums[idx] = -nums[idx]
        }
    }
    result := []int{}
    for i, x := range nums {
        if x > 0 {
            result = append(result, i+1)
        }
    }
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

pub fn find_disappeared_numbers(mut nums: Vec<i32>) -> Vec<i32> {
    for i in 0..nums.len() {
        let idx = nums[i].unsigned_abs() as usize - 1;
        if nums[idx] > 0 {
            nums[idx] = -nums[idx];
        }
    }
    nums.iter()
        .enumerate()
        .filter(|(_, &x)| x > 0)
        .map(|(i, _)| i as i32 + 1)
        .collect()
}

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

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

复杂度

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

可以迁移的模式

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

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