找到所有数组中消失的数字 图解题解

这道题真正在问什么

数组长度为 n，每个元素都落在 1 到 n 之间、可能重复，要求找出 1 到 n 中没出现在数组里的所有数。比如 [4,3,2,7,8,2,3,1] 里，5 和 6 从没露过面。题目附加的挑战是 O(n) 时间加 O(1) 额外空间——这条限制把最顺手的哈希集合排除在外，正是整道题的题眼。

哈希集合为什么不达标，突破口在哪

把出现过的数装进哈希集合，再从 1 到 n 逐个查缺，时间 O(n) 没问题，但集合要 O(n) 空间。想省掉这份空间，就得注意题目埋下的巧合：值域是 1 到 n，数组下标是 0 到 n-1，两者一一对应——值 v 天然对应下标 v-1。也就是说，数组自身就能充当那张「出勤表」，每个格子负责登记一个值来没来过，不需要另开任何结构。

负号凭什么能当标记用

出勤表需要在每个格子里记一个「来过或没来过」的标志位，可格子里已经存着原数据了。妙处在于：题目保证所有值都是正数，符号位是闲置的信息通道。把某格翻成负数，表示「它负责的那个值出现过」；而随时取绝对值就能还原原值——标记和数据挤在同一个格子里互不干扰，这正是 O(1) 空间的来源。

两遍扫描各自为什么成立

第一遍打卡：读到一个数先取绝对值（它可能已被前面的操作翻成负数），定位到下标 |x|-1，只在那一格还是正数时才翻负。「只翻一次」很关键——重复值会两次定位到同一个格子，无脑取反会把负号翻回正数，擦掉已有的打卡记录。

第二遍收集：扫完之后某格仍是正数，说明从头到尾没有任何数来给它打过卡，它负责的值（下标加一）就从未出现过，收进答案。每个格子的符号忠实记录了对应值出现与否，所以答案不重不漏。

复杂度与这套技巧的适用边界

时间 O(n)：标记一遍加收集一遍，两趟线性扫描。额外空间 O(1)：借的是输入数组自己的符号位，返回数组按惯例不计。要注意这套原地标记的前提是「值域与下标同构」：值域里出现 0、负数或远超 n 的数就借不了位，只能退回哈希集合的 O(n) 空间方案；另外它改写了输入数组，如果调用方要求输入只读，同样得换普通做法。

Python

def findDisappearedNumbers(nums):
    n = len(nums)
    for x in nums:               # 第一遍：标记
        idx = abs(x) - 1         # 值 x 对应下标
        if nums[idx] > 0:        # 只在还是正数时翻负
            nums[idx] = -nums[idx]
    res = []
    for i in range(n):           # 第二遍：收集
        if nums[i] > 0:          # 仍为正 → 值 i+1 没出现
            res.append(i + 1)
    return res

C++

vector<int> findDisappearedNumbers(vector<int>& nums){
    int n = nums.size();
    for (int x : nums) {              // 第一遍：标记
        int idx = abs(x) - 1;        // 值对应下标
        if (nums[idx] > 0)           // 仍为正才翻负
            nums[idx] = -nums[idx];
    }
    vector<int> res;
    for (int i = 0; i < n; i++)      // 第二遍：收集
        if (nums[i] > 0) res.push_back(i + 1);
    return res;
}

Java

public List<Integer> findDisappearedNumbers(int[] nums) {
    int n = nums.length;
    for (int x : nums) {              // 第一遍：标记
        int idx = Math.abs(x) - 1;   // 值对应下标
        if (nums[idx] > 0) {         // 仍为正才翻负
            nums[idx] = -nums[idx];
        }
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {     // 第二遍：收集
        if (nums[i] > 0) res.add(i + 1);
    }
    return res;
}