数组中重复的数据 图解题解

这道题到底在问什么

输入

nums=[4,3,2,7,8,2,3,1]

输出

[2,3]　（2 和 3 各出现两次）

输入

nums=[1,1,2]

输出

[1]

最优解：一步一步想明白

1. 3记牢这套「取绝对值 → 看 x-1 格子 → 负则重复、正则翻负打卡」，下面每一帧都在套它。
2. 4开局：数组全是正数，没有任何打卡。值域 1 到 8 正好对应下标 0 到 7，这是整套技巧成立的前提。
3. 5先看懂动作：读到值 4，就跑去下标 3（值 4 的「专属格子」），等下把那里翻成负号当打卡记号。每个值都去敲自己对应的那一格。
4. 6轮到第 0 位，值是 4，所以 x=4，跳去看它的专属格子 下标 3。
5. 7下标 3 还是正的，第一次来：把它翻成负号 -7（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
6. 8轮到第 1 位，值是 3，所以 x=3，跳去看它的专属格子 下标 2。
7. 9下标 2 还是正的，第一次来：把它翻成负号 -2（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
8. 10轮到第 2 位，值是 -2（先前被翻过负，取绝对值），所以 x=2，跳去看它的专属格子 下标 1。
9. 11下标 1 还是正的，第一次来：把它翻成负号 -3（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
10. 12轮到第 3 位，值是 -7（先前被翻过负，取绝对值），所以 x=7，跳去看它的专属格子 下标 6。
11. 13下标 6 还是正的，第一次来：把它翻成负号 -3（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
12. 14轮到第 4 位，值是 8，所以 x=8，跳去看它的专属格子 下标 7。
13. 15下标 7 还是正的，第一次来：把它翻成负号 -1（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
14. 16轮到第 5 位，值是 2，所以 x=2，跳去看它的专属格子 下标 1。
15. 17下标 1 的格子已经是负的（红色）——说明 2 早就打过卡了，这就是出现两次的数，收进答案：{ 2 }。
16. 18轮到第 6 位，值是 -3（先前被翻过负，取绝对值），所以 x=3，跳去看它的专属格子 下标 2。
17. 19下标 2 的格子已经是负的（红色）——说明 3 早就打过卡了，这就是出现两次的数，收进答案：{ 2, 3 }。
18. 20轮到第 7 位，值是 -1（先前被翻过负，取绝对值），所以 x=1，跳去看它的专属格子 下标 0。
19. 21下标 0 还是正的，第一次来：把它翻成负号 -4（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。
20. 22八个位置全扫完。回头看，凡是负号的格子都被打过卡，整张数组本身就当了哈希表用，没多花一格额外空间。
21. 23揭晓：出现两次的是 2 和 3，答案 [2, 3]，和开头说的一致。整趟只走了一遍数组、没开额外数组，时间 O(n)、空间 O(1)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        for x in nums:
            idx = abs(x) - 1
            if nums[idx] < 0:
                ans.append(idx + 1)
            else:
                nums[idx] = -nums[idx]
        return ans

#include <cstdlib>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int x : nums) {
            int idx = abs(x) - 1;
            if (nums[idx] < 0) ans.push_back(idx + 1);
            else nums[idx] = -nums[idx];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for (int x : nums) {
            int idx = Math.abs(x) - 1;
            if (nums[idx] < 0) ans.add(idx + 1);
            else nums[idx] = -nums[idx];
        }
        return ans;
    }
}

复杂度

面试官可能追问