在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

kdn251/面试

菜单

哈希表问题

相关源文件

介绍

本文档涵盖了技术面试中常见的基于哈希表的问题及其解决方案。哈希表是一种重要的数据结构，以其O(1)平均时间复杂度的查找、插入和删除操作而闻名，这使得它们在高效解决各种算法问题时特别有用。

有关哈希表实现详情，请参阅哈希表。

来源

哈希表问题模式

哈希表擅长解决以下几类问题：

  1. 检测重复项：快速识别集合中的重复元素
  2. 频率计数：跟踪元素出现的频率
  3. 查找和映射：在值之间创建高效映射
  4. 查找唯一元素：识别只出现一次或具有特定出现模式的元素

下图展示了哈希表问题的常见模式结构：

来源：leetcode/hash-table/ContainsDuplicate.java leetcode/hash-table/FirstUniqueCharacterInAString.java leetcode/hash-table/EncodeAndDecodeTinyURL.java

示例问题：判断重复

问题描述

给定一个整数数组，判断数组中是否存在重复元素。如果数组中存在至少出现两次的值，则函数应返回true；如果每个元素都互不相同，则返回false。

解决方案方法

该解决方案使用哈希表来跟踪遍历数组时遇到的元素。对于每个元素，我们检查它是否已存在于哈希表中——如果存在，则找到了重复项；如果不存在，则将其添加到哈希表。

实现

该解决方案在containsDuplicate方法中实现：

  1. 创建一个HashMap来跟踪元素
  2. 遍历数组
  3. 对于每个元素，检查它是否已存在于映射中
  4. 如果找到，返回true（检测到重复项）
  5. 如果未找到，将其添加到映射中
  6. 如果循环完成未返回，则返回false（无重复项）

时间复杂度：O(n)，其中 n 是数组长度 空间复杂度：O(n)，用于在哈希映射中存储元素

来源：leetcode/hash-table/ContainsDuplicate.java4-17

示例问题：字符串中的第一个唯一字符

问题描述

给定一个字符串，找到第一个不重复的字符并返回其索引。如果不存在此类字符，则返回 -1。

解决方案方法

此问题采用两趟遍历方法，使用哈希表来计算字符出现次数：

  1. 第一趟：构建一个哈希映射，记录每个字符的索引或将其标记为重复项
  2. 第二趟：找到具有最小有效索引的字符

实现

该解决方案使用HashMap类来存储字符索引：

  • 如果字符首次出现，存储其索引
  • 如果字符再次出现，将其标记为 -1（表示它不唯一）
  • 找到最小的有效索引（表示第一个不重复的字符）

时间复杂度：O(n)，其中 n 是字符串长度（两次遍历数据） 空间复杂度：O(k)，其中 k 是字符集的大小（对于小写字母最多为 26）

来源：leetcode/hash-table/FirstUniqueCharacterInAString.java12-34

示例问题：TinyURL 的编码与解码

问题描述

设计一个类似 TinyURL 的短链接服务，它能为较长的 URL 提供缩短的 URL。该服务应支持将 URL 编码为短形式，以及将短 URL 解码回其原始形式。

解决方案方法

该实现使用哈希表来维护生成的短 URL 及其对应的原始 URL 之间的映射：

  1. 对于编码：生成一个唯一键并将其映射到原始 URL
  2. 对于解码：使用短 URL 中的键检索原始 URL

实现细节

该解决方案利用了：

  • 一个HashMap，用于存储短 URL 键和原始 URL 之间的映射
  • 一个计数器和字符集来生成唯一键
  • 编码和解码 URL 的方法

键生成方法根据计数器值，使用预定义字符集中的字符创建唯一字符串。

时间复杂度

  • 编码：哈希表操作的平均时间复杂度为 O(1)
  • 解码：哈希表查找的平均时间复杂度为 O(1)

空间复杂度：O(n)，其中 n 是已编码 URL 的数量

来源：leetcode/hash-table/EncodeAndDecodeTinyURL.java8-37

通用模式和技术

使用哈希表进行查找

下表总结了在面试问题中使用哈希表的关键技巧：

技术目的示例
跟踪已见元素检测重复项ContainsDuplicate
计数频率跟踪元素出现次数FirstUniqueCharacterInAString
键值映射创建值之间的关联EncodeAndDecodeTinyURL
两趟遍历法先构建映射，然后查询FirstUniqueCharacterInAString

时间-空间权衡

哈希表解决方案通常以空间换取时间

来源：leetcode/hash-table/ContainsDuplicate.java leetcode/hash-table/FirstUniqueCharacterInAString.java leetcode/hash-table/EncodeAndDecodeTinyURL.java

总结

哈希表问题在技术面试中频繁出现，因为它们考察候选人以下能力：

  1. 识别何时哈希表是合适的数据结构
  2. 使用哈希表操作高效实现解决方案
  3. 分析时间和空间复杂度的权衡

在处理哈希表问题时，请考虑：

  • 需要将什么作为键和值存储
  • 如何处理冲突或重复项
  • 是否需要单次遍历或多次遍历数据
  • 哈希表是否真的是最有效的解决方案（与其他数据结构相比）

来源：leetcode/hash-table/ContainsDuplicate.java leetcode/hash-table/FirstUniqueCharacterInAString.java leetcode/hash-table/EncodeAndDecodeTinyURL.java