287.py

'''
 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.

 Example 1:

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

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

classSolution(object):
deffindDuplicate(self, nums):
"""
 :type nums: List[int]
 :rtype: int
 """
slow, fast=nums[0], nums[0]
whileTrue:
slow=nums[slow]
fast=nums[nums[fast]]
ifslow==fast:
break

num1=nums[0]
num2=slow
whilenum1!=num2:
num1=nums[num1]
num2=nums[num2]
returnnum2