LeetCode Hot 100 | 100. 寻找重复数

核心思路：原地哈希（正负标记法）

本题的关键在于利用 数组下标与值的映射关系 进行原地标记。

核心观察：

• 数组长度为 n + 1，元素值范围是 [1, n]
• 这意味着每个元素的值都可以作为数组下标（减 1 后）
• 例如：值为 3 的元素，对应下标 2（即 nums[2]）

算法思想（原地哈希）：

遍历数组，对于每个元素 nums[i]：

1. 计算其映射位置：target_idx = abs(nums[i]) - 1
2. 检查 nums[target_idx] 的符号：
   • 如果为正：说明是第一次访问，将其标记为负（-nums[target_idx]）
   • 如果为负：说明之前已经被标记过，这个数就是重复的

为什么用负数标记？

• 需要保留原始数值信息（用于计算下一个映射位置）
• 同时需要标记「是否已访问」的状态
• 取负操作既保留了绝对值，又添加了标记

代码实现

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            // 取绝对值，因为元素可能已经被标记为负数
            int num = abs(nums[i]);
            int target_idx = num - 1;  // 值对应下标（值范围 1~n，下标范围 0~n-1）
            
            // 检查目标位置是否已经被标记
            if (nums[target_idx] < 0) {
                return num;  // 已经是负数，说明 num 之前出现过
            }
            
            // 标记目标位置为负数
            nums[target_idx] = -abs(nums[target_idx]);
        }
        
        return 0;  // 根据题意，这行不会执行到
    }
};

关键细节备忘

1. 为什么要用 abs(nums[i])？

   • 当前遍历到的元素可能已经被之前的操作标记为负数
   • 必须用绝对值还原原始数值，才能正确计算映射下标

2. 为什么要用 -abs(nums[target_idx])？

   • 目标位置可能已经是负数（被其他相同值标记过）
   • 需要保留负号，因此先取绝对值再取负

3. 类似题目关联：

   • LeetCode 41. 第一个缺失的正数：同样的原地哈希思想
   • 核心模式：「值在 [1, n] 范围内，数组长度为 n」→ 考虑原地哈希

4. 进阶解法 —— Floyd 判圈算法（快慢指针）：

   • 把数组看作链表：i → nums[i]
   • 由于有重复元素，链表中一定存在环
   • 快慢指针找到环的入口，即为重复数
   • 时间复杂度：$O(N)$ — 不需要修改数组
   • 空间复杂度：$O(1)$ — 只使用两个指针

5. 复杂度分析（当前解法）：

   • 时间复杂度：$O(N)$ — 只需遍历一次
   • 空间复杂度：$O(1)$ — 原地操作，但会修改输入数组
   • 副作用：修改了原数组，如果要求不能修改，需使用 Floyd 算法