217.Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
1
2
| Input: nums = [1,2,3,1]
Output: true
|
Example 2:
1
2
| Input: nums = [1,2,3,4]
Output: false
|
Example 3:
1
2
| Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
|
排序法：
时间复杂度：O(nlogn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int nums_size = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < nums_size - 1; i++) {
if (nums[i] == nums[i + 1])return true;
}
return false;
}
};
|
哈希表：
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for (int num : nums) {
if (hash.count(num))return true;
else hash.insert(num);
}
return false;
}
};
|