一、问题描述

二、解题思路

解法一：排序+搜索

首先，对nums向量进行一个排序，重复出现的数字会挨在一起，进行搜索即可。

解法二：哈希统计频率

使用哈希表来统计每个数字出现的次数，如果某一数字出现次数超过1次，返回即可。

解法三：快慢双指针

由于本题的数字的范围为[0,n]，数组的下标为[0,n]，经过分析可以得知本题实质上是在找环的入口，可以使用快慢双指针来解决：

(1)首先，初始化slow指针为nums[0]，fast指针为nums[nums[0]]，slow指针每次走一步，fast指针每次走两步，直至slow==fast；

(2)再定义一个新指针ptr，初始化为nums[0]，ptr和fast每次走一步，直至二者相遇，返回此时的ptr，即为所求。

三、代码实现

解法一：排序+搜索

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //排序+搜索
        sort(nums.begin(),nums.end());
        for(int i=0;i!=nums.size()-1;i++)
            if(nums[i]==nums[i+1]) return nums[i];
        return -1;
    }
};

解法二：哈希统计频率

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //哈希表
        unordered_map<int,int> hash;
        for(auto x:nums){
            hash[x]++;
            if(hash[x]>1) return x;
        }
        return -1;
    }
};

解法三：快慢双指针

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 快慢双指针
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        // 第一阶段：找到环中的相遇点
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        // 第二阶段：找到环的入口（重复的数字）
        int ptr = 0;
        while (ptr != slow) {
            ptr = nums[ptr];
            slow = nums[slow];
        }
        
        return ptr;
    }
};