287.寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2
示例 2：

输入：nums = [3,1,3,4,2]
输出：3
示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

题解

class Solution {
    public int findDuplicate(int[] nums) {
        if(nums==null||nums.length<2) return -1;
        int slow = nums[0];
        int fast = nums[nums[0]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast=0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

/*
 * 核心思路：Floyd 判圈算法（快慢指针）
 * * 1. 【抽象建模】：将数组视为一个链表
 * - 节点：数组的下标（Index）。
 * - 指针（Next）：数组的值（Value）。即节点 i 指向节点 nums[i]。
 * * 2. 【为什么会有环？】
 * - 题目给定 n+1 个数，数值范围在 [1, n]。
 * - 根据“鸽巢原理”，必然至少有一个数是重复的。
 * - 重复的数字意味着：有两个不同的下标（节点）指向了同一个数值（下一个节点）。
 * - 这种“多对一”的指向关系，在链表结构中就形成了环，而这个重复的数值就是“环的入口”。
 * * 3. 【算法步骤】
 * - 步骤一（判圈）：
 * 定义快慢指针，slow 每次走1步，fast 每次走2步。
 * 如果链表有环，fast 最终会在环内追上 slow（首次相遇）。
 * * - 步骤二（找入口）：
 * 相遇后，将 fast 重置回起点（索引0），slow 保持在相遇点。
 * 两者改为每次都只走1步。
 * 根据数学推导（见下方证明），它们再次相遇的位置，就是环的入口（即重复数）。
 */

        // 证明：
// 设起点到环入口距离为 x，环入口到相遇点为 y，环长为 L，相遇点到环入口剩余距离为 z (即 L = y + z)。
// 1. 快慢指针相遇时：
//    慢指针路程：x + y
//    快指针路程：x + y + nL (多走了 n 圈)
// 2. 速度关系：2 * (x + y) = x + y + nL
// 3. 化简得：x + y = nL  =>  x = nL - y
// 4. 这里的 nL - y 可以理解为：转了 n-1 圈后，再走 L-y 的距离。
//    而 L-y 正好等于 z。
// 5. 结论：x = (n-1)L + z。
//    这意味着：从起点走 x 步，和从相遇点走 z 步，最终都会到达环入口。