> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/untitled.md).

# 287. Find the Duplicate Number

\# Medium

{% hint style="info" %}
特别难想到。

**key: Floyd's Tortoise and Hare (Cycle Detection)**

Very similar to #142 [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/solution/)
{% endhint %}

{% tabs %}
{% tab title="Python" %}

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

Time complexity = $$O(n)$$ , space complexity = $$O(1)$$ 
{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}