LeetCode217. 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.
Example 1:

1
2
Input: [1,2,3,1]
Output: true

Example 2:

1
2
Input: [1,2,3,4]
Output: false

Example 3:

1
2
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true


1


Hash Table

用无序关联式容器unordered_map记录数字出现的次数,key是数字,value代表数字出现的次数。用find(key)或者count(key)可以验证是否有重复数字。

my code in cpp

1
2
3
4
5
6
7
8
9
10
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> m;
for(int i=0;i<nums.size();i++)
{
//if(m.find(nums[i])!=m.end()) return true;
if(m.count(nums[i])!=0) return true;
++m[nums[i]];
}
return false;
}

Sort

排序过后,比较两个相邻的数字是否相同,如果相同,就说明有重复数字。

my code in cpp

1
2
3
4
5
6
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i=1;i<nums.size();i++)
if(nums[i]==nums[i-1]) return true;
return false;
}
Thanks for Support.