> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/287.-find-the-duplicate-number.md).

# 287. Find the Duplicate Number

Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive.

There is only **one repeated number** in `nums`, return *this repeated number*.

You must solve the problem **without** modifying the array `nums` and using only constant extra space.

 

**Example 1:**

<pre><code><strong>Input: nums = [1,3,4,2,2]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,1,3,4,2]
</strong><strong>Output: 3
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [3,3,3,3,3]
</strong><strong>Output: 3
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 10`<sup>`5`</sup>
* `nums.length == n + 1`
* `1 <= nums[i] <= n`
* All the integers in `nums` appear only **once** except for **precisely one integer** which appears **two or more** times.

分析

1. **关键观察**：
   * 将数组索引和值看作链表节点：
     * 索引 `i` 指向 `nums[i]`
     * 例如 `nums = [1,3,4,2,2]` 可转化为：

       CopyDownload

       ```
       0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
       ```
2. **重复数必然形成环**：
   * 因为有重复数字，必然存在至少两个索引指向同一个值
   * 这会导致链表出现环（如示例中 `2 → 4 → 2` 的环）

<br>

```
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow


```