217. Contains Duplicate

判断一个数组中是否存在相同元素的题目。 描述： Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. 意为：给出一个int型数组，找出是否有重复的元素，有的话返回true，没重复元素返回false。

给出的Tags是array和hash table，所以考虑用这两种方法来做：

先排序后比较前后元素是否相等

class Solution { public: bool containsDuplicate(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i = 1;i < nums.size();i++){ if(nums[i-1] == nums[i]){ return true; } } return false; } };

python：

class Solution(object): def containsDuplicate(self, nums): nums.sort() i = 1 while i < len(nums): if nums[i-1] == nums[i]: return True i+=1 return False

hash_map

第二种就是使用hash表了，我们知道hash通常也都是用来判重去重的，因为它的key是唯一的，我们可以用key的有无来判断某个元素的存在。

class Solution { public: bool containsDuplicate(vector<int>& nums) { //这个unordered_map是hash_map的升级版，在c++11中提出的 unordered_map<int,bool> hash; for(int i = 0;i < nums.size();i++){ if(hash.count(nums[i])){return true;} hash[nums[i]] = true; } return false; } };

python中也有相似的结构dict字典，支持键值对存储：

class Solution(object): def containsDuplicate(self, nums): res = {} nums.sort() for i in nums: if i in res: return True else: res[i] = 0 return False