leetcode【每日一题】287. 寻找重复数 Java

我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode

题干

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
1
2

示例 2:

输入: [3,1,3,4,2]
输出: 3
1
2

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

想法

就是找重复，如果没有附加条件方法就多了，排序 hahset都行。
但是这些有这些要求，那么很容易联想到
数组就想一个跑道，跑道？是不是有点像弗洛伊德龟兔算法？
乌龟每次跑一步，兔子每次跑两部。
因为有重复的数，那么就有至少两个节点指向重复元素。
意思是这里边存在环，
龟兔赛跑会遇到
又因为 其数字都在 1 到 n 之间
所以nums[i]一定在1到n之前，不会越界。

我们画个图
我们可以知道 现在c=a
于是现在把