-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathArray-217-Contains Duplicate
33 lines (33 loc) · 1.31 KB
/
Array-217-Contains Duplicate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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.
=======================================
class Solution {
public boolean containsDuplicate(int[] nums) {
int len = nums.length;
if(len < 2){
return false;
}
int max = nums[0];
int min = nums[len - 1]; //找出nums的最大值和最小值
for(int v : nums){
if(v > max)
max = v;
else if(v < min)
min = v;
}
boolean[] hash = new boolean[max - min + 1]; //用最大值最小值的差值+1的空间大小建立散列空间
for(int v : nums){
if(hash[v - min]){ //此值没进行过散列
return true;
}
else{
hash[v - min] = true; //进行过散列, 即重复
}
}
return false;
}
}
//3ms, 99%
//查看了lc上面的耗时分布,非常有意思, 一点小小的改动也会对耗时产生较大影响:
//Hash数组(3ms-5ms) < Arrays.sort(5ms-9ms) < HashSet + set.add()返回值(13ms-16ms)< HashSet全部转化 + 利用set.size()(16ms-18ms) < HashSet + set.contains()返回值(18ms-25+ms)