哈希法：
时间复杂度 ： $O(N)$
空间复杂度 ： $O(N)$

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        unordered_map <int, bool> hash;

        for (int x : nums)
            if (x < 0 || x >= nums.size())
                return -1;

        for (int x : nums)
        {
            if (hash[x]) return x;
            hash[x] = true;
        }

        return -1;
    }
};

原地交换法：
时间复杂度 ： $O(N)$
空间复杂度 ： $O(1)$

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();

        for (int x : nums)
            if (x < 0 || x >= n) return -1;

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

        return -1;
    }
};