算法1

(哈希表统计次数) $O(n)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 判断边界条件
        for(auto e : nums)
        {
            if(e < 0 || e > nums.size() - 1)
                return -1;
        }

        // 哈希表统计数字个数
        int n = nums.size();
        unordered_map<int, int> hash(n);

        for(auto e : nums)
        {
            hash[e]++;
            if(hash[e] >= 2)
            {
                return e;
            }
        }

        return -1;
    }
};

算法2

(交换法) $O(n)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 判断边界条件
        int n = nums.size();
        for(auto e : nums)
        {
            if(e < 0 || e > n - 1)
                return -1;
        }

        // 交换法
        for(int i = 0; i < n; ++i)
        {
            while(i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if(i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];
        }

        return -1;
    }
};