LeetCode 705. 设计哈希集合
题目描述
题意分析
不使用内建哈希表，实现整数集合的
add、remove和contains。集合只关心某个键是否存在，重复添加不增加副本，删除不存在的键也不产生影响。题目保证键位于闭区间[0, 1000000]。
解法：固定域布尔数组
核心思路
[!blue]
键的范围固定且可以直接作为数组下标，因此给每个合法键分配一个布尔位置即可。定义
data[key]为“键key当前是否属于集合”：true表示存在，false表示不存在。不同键访问不同位置，不会产生哈希冲突。构造时数组默认全为
false，对应空集合。添加把对应位置设为true，删除设为false，查询直接返回该值；这三种操作都恰好保持上述含义。重复设置同一个布尔值不会改变结果，因此集合的去重和无效删除不需要额外判断。这里利用固定值域直接寻址，空间按所有可能的键分配，而非按实际已存入的键数分配。
解题步骤
- 构造时分配
1_000_001个布尔位置，覆盖下标 0 到1_000_000，初始都为false。add(key)执行data[key] = true。remove(key)执行data[key] = false。contains(key)返回data[key]。数组由每个实例独立创建，因此一个集合的修改不会影响另一个集合。最小键 0 和最大键
1_000_000与其他键使用完全相同的操作。
代码实现
class MyHashSet {
// data 的对应位置表示该键当前是否属于集合
private final boolean[] data;
public MyHashSet() {
// 键范围包含零与最大值，分配上界加一的位置
data = new boolean[1_000_001];
}
public void add(int key) {
data[key] = true;
}
public void remove(int key) {
data[key] = false;
}
public boolean contains(int key) {
return data[key];
}
}
type MyHashSet struct {
// data 的对应位置表示该键当前是否属于集合
data []bool
}
func ConstructorMyHashSet() MyHashSet {
// 键范围包含零与最大值，分配上界加一的位置
return MyHashSet{data: make([]bool, 1_000_001)}
}
func (this *MyHashSet) Add(key int) {
this.data[key] = true
}
func (this *MyHashSet) Remove(key int) {
this.data[key] = false
}
func (this *MyHashSet) Contains(key int) bool {
return this.data[key]
}
复杂度分析
- 时间复杂度：构造为 $O(V)$，需要分配并初始化数组；添加、删除、查询最坏均为 $O(1)$。$V$ 为值域大小。
- 空间复杂度：$O(V)$，本题为
1_000_001个布尔位置。
关键点总结
[!green]
- 集合只记录存在性，不记录重复添加次数。
- 值域闭区间两端都必须有对应下标。
易错点总结
[!yellow]
- 少分配一个位置，会在最大合法键处越界。
- 重复添加做次数累加、删除只减一，会实现成多重集合。
- 多个实例共享同一状态数组，会相互影响集合内容。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 706. 设计哈希映射 | 简单 | 本题只保存键的存在性，原题还要为键关联可更新的值，冲突组织方式可复用。 |
| 217. 存在重复元素 | 简单 | 重复元素判断依赖高效集合查询，本题实现其底层基本接口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！