287.md

[287] Find the Duplicate Number

Description

link

---

Solution

• See Code

---

Code

O(n)

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