LeetCode 287. 寻找重复数

给定一个包含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中只有一个整数出现两次或多次，其余整数均只出现一次

class Solution { public: int findDuplicate(vector<int>& nums) { int slow =nums[0]; int fast =nums[0]; do { slow=nums[slow]; fast=nums[nums[fast]]; }while(slow!=fast); slow=nums[0]; while(slow!=fast) { slow=nums[slow]; fast=nums[fast]; } return slow; } };