Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Input: [1,3,4,2,2]
Output: 2

1.You must not modify the array (assume the array is read only).

2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

要求1、2，所以不能排序。

方法1. count

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums.count(nums[i])>1:
                return(nums[i])

很简单，但是表现不好。
Runtime: 4368 ms, faster than 5.15% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 15.2 MB, less than 17.86% of Python3 online submissions for Find the Duplicate Number.

方法2. 用链表

• nums[a] = b means a.next = b
• Example: [2,5,1,1,4,3]. Model a graph using the indices of this array. If there is a duplicate b, then we will have a1.next = b and a2.next = b and a3.next = b .....Sketch a graph for the above.
• 可以想象成有两个pointer，一个走得快一个走得慢，在绕同一个cycle走。假设存在重复数字，则会在环内相遇，假设不存在重复数字，形成循环链表，在头结点相遇

class Solution(object):
    def findDuplicate(self, nums):
        slow = 0
        fast = 0
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if slow == fast:
                break
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

Runtime: 56 ms, faster than 98.62% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 15.2 MB, less than 17.86% of Python3 online submissions for Find the Duplicate Number.