Problem: 287. 寻找重复数

整体思路

这段代码旨在解决一个经典的数组问题：寻找重复数 (Find the Duplicate Number)。问题描述通常是：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 的范围内（包含 1 和 n），可知至少存在一个重复的整数。要求找出这个重复的数，并且通常有附加条件：不能修改原数组，且只能使用 O(1) 的额外空间。

该算法将这个数组问题抽象成了一个链表环检测问题。

1. 构建隐式链表：

   • 算法将数组的索引视为链表的节点。
   • 数组中在某个索引 i 处的值 nums[i] 被视为从节点 i 指向下一个节点 nums[i] 的指针。
   • 因此，我们可以从索引 0 开始，形成一个访问序列：0 -> nums[0] -> nums[nums[0]] -> ...。
   • 为什么一定有环？ 因为数组中有 n+1 个数字（来自 nums[0] 到 nums[n]），但它们的值都在 1 到 n 的范围内。根据鸽巢原理，至少有两个不同的索引 i 和 j，它们的值相同，即 nums[i] = nums[j]。这意味着在我们的隐式链表中，有两个不同的节点（i 和 j）都指向了同一个下一个节点，这必然会形成一个环。
   • 环的入口是什么？ 这个环的入口节点（索引）正是那个重复的数字。因为当序列第一次访问到一个已经被访问过的索引时，这个索引就是重复值，环也就从此开始。

2. Floyd 环检测算法：

   • 该算法分两个阶段来找到环的入口。
   • 阶段一：找到环内的相遇点
     • 设置两个指针，slow 和 fast。slow 每次移动一步 (slow = nums[slow])，fast 每次移动两步 (fast = nums[nums[fast]])。
     • 它们从起点开始赛跑。由于 fast 比 slow 快，如果链表中存在环，fast 最终会从后面追上 slow，两者在环内的某个点相遇。第一个 while 循环就是为了找到这个相遇点。
   • 阶段二：找到环的入口点
     • 这是算法最巧妙的部分。当 slow 和 fast 相遇后，我们将其中一个指针（代码中是circle = slow）留在相遇点，同时派出另一个新指针 line 从链表的起点（索引 0）出发。
     • 现在，让 line 和 circle 两个指针都以相同的速度（每次一步）前进。
     • 一个数学上的结论是：这两个指针必定会在环的入口点相遇。
     • 第二个 while 循环就是为了找到这个新的相遇点。

3. 返回结果：

   • 当 line 和 circle 相遇时，它们所在的索引就是环的入口，也就是那个重复的数字。算法返回这个值。

完整代码

class Solution {
    /**
     * 在一个包含 n+1 个整数（范围1到n）的数组中找到重复的数字。
     * @param nums 整数数组
     * @return 重复的数字
     */
    public int findDuplicate(int[] nums) {
        // --- 阶段一：找到环中的相遇点 ---
        // 将数组看作一个隐式链表，nums[i] 是从索引 i 指向下一个索引的指针。
        
        // slow 指针，每次移动一步。
        int slow = nums[0];
        // fast 指针，每次移动两步。
        int fast = nums[nums[0]];
        
        // 循环直到 slow 和 fast 相遇。
        // 因为题目保证有重复数，所以一定存在环，这个循环一定会终止。
        while (slow != fast) {
            slow = nums[slow];           // slow 走一步
            fast = nums[nums[fast]];     // fast 走两步
        }

        // --- 阶段二：找到环的入口点 ---
        // 此时，slow 和 fast 在环内的某一点相遇。
        
        // line 指针，从链表起点（索引0）开始。
        int line = 0;
        // circle 指针，从刚才的相遇点开始。
        int circle = slow;
        
        // 两个指针都以相同的速度（每次一步）前进，直到它们相遇。
        while (line != circle) {
            circle = nums[circle];
            line = nums[line];
        }
        
        // 它们相遇的节点就是环的入口，即重复的数字。
        return line;
    }
}

时空复杂度

时间复杂度：O(N)

1. 阶段一（找到相遇点）：
   • slow 指针和 fast 指针在数组中移动。slow 指针进入环之前最多走 N 步，进入环之后，fast 指针最多比 slow 指针多走一圈（长度小于 N）就能追上它。因此，slow 指针走过的总步数是 O(N) 级别的。
2. 阶段二（找到环入口）：
   • line 指针从索引 0 开始走到环入口，走的步数是环前面“直路”的长度。
   • circle 指针从相遇点开始走到环入口。
   • 这两个指针走的总步数也是 O(N) 级别的。

综合分析：
整个算法由两个独立的、不嵌套的线性扫描组成。总的时间复杂度是 O(N) + O(N) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：该算法没有创建任何与输入规模 N 成比例的新的数据结构（如辅助数组、哈希表等）。
2. 辅助变量：只使用了 slow, fast, line, circle 等几个固定数量的整型变量。

综合分析：
算法的所有操作都是在原数组上进行读取（没有修改），所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。