数组：我不只是数组，我还能兼职 HashMap

2502_94273177

445人浏览 · 2026-05-12 13:39:25

2502_94273177 · 2026-05-12 13:39:25 发布

如何同时寻找缺失和重复的元素？这题把数组当“记事本”用了

刷题的时候经常有一种感觉：

“这题我会，但是面试官肯定不满意。”

比如这道经典题：

给你一个长度为 n 的数组，本来应该装着 1~n 这 n 个数，结果现在：

一个数字重复了
一个数字丢了

让你找出来。

比如：

nums = [1,2,2,4]

很明显：

2 重复了
3 消失了

[2,3]

很多人第一反应：

HashMap 统计次数

当然能做。

但这题真正阴险的地方在于：

它故意把数字范围限制成了 1~n

这说明：

出题人不想让你老老实实开哈希表。

他想让你——

直接拿原数组当哈希表使。

这才是这题最骚的地方。

一、数组和下标，其实天生就是映射关系

因为数组里只有 1~n。

所以：

数字	对应下标
1	0
2	1
3	2

也就是说：

数字 x  ->  下标 x-1

这就很关键了。

因为我们突然发现：

“出现过没” 这个信息，其实可以直接记录到数组对应位置上。

二、怎么记录“出现过”？

答案非常抽象：

把对应位置改成负数。

比如：

nums = [1,2,2,4]

我们开始遍历。

先看数字 1

它应该对应：

index = 1 - 1 = 0

于是：

nums[0] *= -1

数组变成：

[-1,2,2,4]

表示：

1 出现过了

再看数字 2

对应：

index = 1

于是：

nums[1] *= -1

数组：

[-1,-2,2,4]

表示：

2 出现过

再看第二个 2

又来到：

index = 1

这时候发现：

nums[1] 已经是负数了

说明什么？

说明：

这里已经有人来过了！

也就是说：

2 重复了

这就是重复元素。

三、那缺失元素怎么找？

最后数组会变成：

[-1,-2,2,-4]

观察一下：

下标	值
0	负
1	负
2	正
3	负

只有：

nums[2]

还是正数。

说明：

3 从来没人访问过

所以：

缺失元素 = 3

四、完整代码

class Solution {
    public int[] findErrorNums(int[] nums) {

        int n = nums.length;

        int dup = -1;

        // 找重复元素
        for (int i = 0; i < n; i++) {

            int index = Math.abs(nums[i]) - 1;

            // 已经访问过
            if (nums[index] < 0) {
                dup = Math.abs(nums[i]);
            } else {
                nums[index] *= -1;
            }
        }

        int missing = -1;

        // 找缺失元素
        for (int i = 0; i < n; i++) {

            // 没访问过
            if (nums[i] > 0) {
                missing = i + 1;
            }
        }

        return new int[]{dup, missing};
    }
}

五、这题真正牛逼的地方

很多人觉得：

“不就是改个符号吗？”

但实际上这题核心思想非常高级：

1、原地哈希

没开哈希表。

但数组本身：

既存数据
又存状态

这就是：

原地哈希（In-place Hashing）

很多经典题都这么干。

2、把“值”映射到“索引”

这是整个算法题里最重要的套路之一。

只要题目出现：

1~n
0~n-1
有限范围

你就应该立刻警觉：

能不能把数字映射到数组下标？

这是高频套路。

六、为什么数字必须从 1 开始？

因为：

0 的相反数还是 0

比如：

0 -> -0

结果还是：

你根本无法判断：

它到底访问过没有

所以这题：

必须从 1 开始

这是题目设计里非常阴的一点。

七、进阶版：LeetCode 41 缺失的第一个正数

这题属于：

“同一个导演拍的续集。”

题目：

找数组里缺失的最小正整数

比如：

[3,4,-1,1]

答案：

八、这题最重要的一步：先想答案范围

数组长度是 n。

那么答案只可能是：

1 ~ n+1

为什么？

因为最完美情况：

[1,2,3,4]

那缺失的就是：

否则：

只要出现垃圾数字：

负数
0
大于 n

那么：

1~n

里一定有人失踪。

九、所以垃圾数字根本不用管

比如：

[7,8,9,11,12]

这些数字：

全部没意义

因为它们不可能影响：

1~n

于是：

我们直接把这些垃圾数字：

全部改成 n+1

相当于：

“滚一边去别碍事。”

十、核心思路还是同一个

依然是：

数字 x
映射到
下标 x-1

然后：

把对应位置改成负数

表示：

x 出现过

十一、完整代码

class Solution {

    public int firstMissingPositive(int[] nums) {

        int n = nums.length;

        // 先清理垃圾数字
        for (int i = 0; i < n; i++) {

            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 标记出现过的数字
        for (int i = 0; i < n; i++) {

            int x = Math.abs(nums[i]);

            if (x <= n) {
                nums[x - 1] = -Math.abs(nums[x - 1]);
            }
        }

        // 找第一个没出现的
        for (int i = 0; i < n; i++) {

            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
}