287.md

287. Find the Duplicate Number

Solution 1 (time O(n), space O(1))

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                p = 0
                while p != slow:
                    p = nums[p]
                    slow = nums[slow]
                return slow