Problem
Given an integer array nums, return true if any value appears at least twice in the array. Otherwise, return false.In other words, we need to determine whether the array contains any duplicate element.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1, 2, 3, 1]Output
trueInput
nums = [1, 2, 3, 4]Output
falseSolution
This solution uses a HashSet to keep track of the elements that have already been encountered while traversing the array.For each element, we first check whether it already exists in the set. If it does, the element is a duplicate, so we return
true. Otherwise, we add the element to the set and continue scanning the array.
If the entire array is traversed without finding a duplicate, we return
false.
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
}Complexity
Each element is inserted into and searched in the HashSet in averageO(1) time. Therefore, the overall time complexity is O(n), where n is the length of the array.
The HashSet can store up to n elements, so the extra space complexity is
O(n).