LeetCode 287. 寻找重复数

Categories:

Tags:

题目描述
思路分析
1. 解法一：Floyd 判圈（推荐）
相似题目

题目描述

✅ 287. 寻找重复数

思路分析

解法一：Floyd 判圈（推荐）

核心思路：

把数组看作链表：索引 i 指向 nums[i]，重复数对应环入口。

先用快慢指针找到相遇点，再从起点与相遇点同步前进，找到入口。

不修改数组，满足 O(1) 空间要求。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // 快慢指针在环内相遇
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        int ptr = nums[0];

        // 从起点与相遇点同步前进找到入口
        while (ptr != slow) {
            ptr = nums[ptr];
            slow = nums[slow];
        }

        return ptr;
    }
}

func findDuplicate(nums []int) int {
    slow, fast := nums[0], nums[0]

    // 快慢指针在环内相遇
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    ptr := nums[0]

    // 从起点与相遇点同步前进找到入口
    for ptr != slow {
        ptr = nums[ptr]
        slow = nums[slow]
    }

    return ptr
}

相似题目

题目	难度	考察点
141. 环形链表	简单	快慢指针
142. 环形链表 II	中等	环入口
442. 数组中重复的数据	中等	原地标记
645. 错误的集合	简单	计数/标记
448. 找到所有数组中消失的数字	简单	原地标记

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/75515068