问题

---

一个长度为n+1的整数数组，其中的元素为[1, n]的整数，其中有一个元素出现两次或更多次，其他元素只出现一次。

要求：

1. 不能改变原数组
2. 时间复杂度O(n)，空间复杂度O(1)

思路

---

如果不要求不改变原数组，可以用上一题找出所有重复数（442）中的方法，将出现过的数进行记录，无需额外空间；
如果不要求空间复杂度，可以用一个集合记录出现过的元素。
两个要求都满足的情况下，可以用弗洛伊德判圈算法（龟兔算法）

算法

---

龟兔算法是用于判断一个链中是否存在环的算法，并可以求出环的长度以及环的起点。
判断方法是：

• 初始两个指针（分别是龟和兔）都指向起点
• 兔每次走两步，龟每次走一步。若龟兔再次相遇（指向同一个节点），则存在环，否则不存在。

寻找环的起点的方法是：

• 上述龟兔再次相遇时，龟返回起点，兔不动。
• 每次龟兔都各走一步，龟兔再次相遇点为起点。

题中所给数组可以看成链表（不一定是一条链），其中下标为节点地址，元素值为下一节点地址next。由于每个节点都有下一节点，即next都不为空，故链表一定有环。

由于元素范围为[1, n]，故下标为0的节点nums[0]不会作为其他节点的下一节点next，因此从0节点开始的链表中一定会存在两个节点的next相同，这个next即为要找的出现两次以上的元素，也就是链表中环的起点。直接套用龟兔算法即可。

代码

---

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