JAVA练习327- 寻找重复数

题目概览

给定一个包含n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。

假设nums只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]输出：2

示例 2：

输入：nums = [3,1,3,4,2]输出：3

示例 3 :

输入：nums = [3,3,3,3,3]输出：3

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums中只有一个整数出现两次或多次，其余整数均只出现一次

进阶：

• 如何证明nums中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度O(n)的解决方案吗？

来源：287. 寻找重复数 - 力扣（LeetCode）

解题分析

方法：快慢指针

此题解法可以参考：JAVA练习294- 环形链表II-CSDN博客 方法二。
因为1 <= nums[i] <= n，因此我们可以用值来进行遍历，以[1,3,4,2,2] 为例子，遍历出的结果就是：1 -> 3 -> 2 -> 4 -> 2-> 4 -> 2 -> ....，可以看出 4->2 成了一个环，因此和上述所说题目一致，参考上面解法即可。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution { public int findDuplicate(int[] nums) { int fast = 0, slow = 0; do { slow = nums[slow]; fast = nums[nums[fast]]; } while(slow != fast); int res = 0; while(res != slow) { res = nums[res]; slow = nums[slow]; } return res; } }