Contains Duplicate
Hash set membership test — return true on the first repeat.
2 min read
hash-set array
Problem#
Return true iff any value appears at least twice in the array.
Examples#
[1,2,3,1]→true.[1,2,3,4]→false;[1,1,1,3,3,4,3,2,4,2]→true.
Constraints#
1 <= nums.length <= 10^5.
Approach#
Walk the array, insert into a hash set. If insertion fails (already present), return true.
Solution#
class Solution {public: bool containsDuplicate(vector<int>& nums) { unordered_set<int> seen; for (int v : nums) { if (!seen.insert(v).second) return true; } return false; }};func containsDuplicate(nums []int) bool { seen := map[int]bool{} for _, v := range nums { if seen[v] { return true } seen[v] = true } return false}from typing import List
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() for v in nums: if v in seen: return True seen.add(v) return Falsefunction containsDuplicate(nums) { const seen = new Set(); for (const v of nums) { if (seen.has(v)) return true; seen.add(v); } return false;}class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int v : nums) { if (!seen.add(v)) return true; } return false; }}function containsDuplicate(nums: number[]): boolean { const seen = new Set<number>(); for (const v of nums) { if (seen.has(v)) return true; seen.add(v); } return false;}Editorial#
insert returns a pair <iterator, bool> where the bool indicates “newly inserted” — a clean one-shot membership-plus-insert. Sorting and adjacent compare gives O(n log n) without extra space, useful if memory is tight.
Complexity#
- Time:
O(n)average. - Space:
O(n).
Concept revision#
Related#