解题思路

这个题很简单，利用了哈希表的性质，判断当前的元素是否在哈希表内，如果在的话，就说明该数是重复的元素，就返回该数。

复杂度

• 时间复杂度：O(n)；
• 空间复杂度：O(n)。

代码

C++

// 写法一
#include <unordered_map>
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        unordered_map<int, int> mp;
	  
        for(int i = 0; i<numbers.size(); i++)
        {
            if(mp.find(numbers[i]) == mp.end())
            {
                mp[numbers[i]]++;
            }
            else {
                return numbers[i];
            }
        }
        return -1;
    }
};


// 写法二
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        map<int, int> mp;

        for(int i = 0; i < numbers.size(); i++)
        {
            if(++mp[numbers[i]] > 1)
            {
                return numbers[i];
            }
        }
        return -1;
    }
};

Python

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        hashList = {}

        for i in numbers:
            if i in hashList:
                return i
            else:
                hashList[i] = 1    
				
        return -1