LeetCode 哈希表搜索题解

LeetCode 哈希表搜索题解

题目描述

实现哈希表搜索算法，在一个整数数组中查找目标值。

示例：

输入：[64, 34, 25, 12, 22, 11, 90]，目标值：22
输出：True（目标值存在于数组中）

解题思路

方法：哈希表搜索

思路：

• 哈希表搜索的核心思想是利用哈希函数将元素映射到哈希表中，从而实现 O(1) 时间复杂度的搜索。
• 具体步骤：
  1. 创建一个哈希表（字典）。
  2. 将数组中的所有元素插入到哈希表中。
  3. 检查目标值是否存在于哈希表中。
  4. 如果存在，返回 True；否则，返回 False。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。插入元素和搜索元素的时间复杂度都是 O(1)。
• 空间复杂度：O(n)，需要额外的空间来存储哈希表。

代码实现

方法：哈希表搜索

# 哈希表搜索 def hash_table_search(arr, target): # 创建哈希表 hash_table = {} # 将数组中的所有元素插入到哈希表中 for num in arr: hash_table[num] = True # 检查目标值是否存在于哈希表中 return target in hash_table # 测试 def test_hash_table_search(): arr = [64, 34, 25, 12, 22, 11, 90] print(hash_table_search(arr, 22)) # 输出：True print(hash_table_search(arr, 100)) # 输出：False print(hash_table_search(arr, 64)) # 输出：True if __name__ == "__main__": test_hash_table_search()

方法：哈希表搜索（返回索引）

# 哈希表搜索（返回索引） def hash_table_search_index(arr, target): # 创建哈希表，存储元素到索引的映射 hash_table = {} for i, num in enumerate(arr): hash_table[num] = i # 检查目标值是否存在于哈希表中 return hash_table.get(target, -1) # 测试 def test_hash_table_search_index(): arr = [64, 34, 25, 12, 22, 11, 90] print(hash_table_search_index(arr, 22)) # 输出：4 print(hash_table_search_index(arr, 100)) # 输出：-1 print(hash_table_search_index(arr, 64)) # 输出：0 if __name__ == "__main__": test_hash_table_search_index()

测试用例

测试用例 1：基本情况

输入：[64, 34, 25, 12, 22, 11, 90]，目标值：22
输出：True

测试用例 2：目标值不存在

输入：[64, 34, 25, 12, 22, 11, 90]，目标值：100
输出：False

测试用例 3：目标值在第一个位置

输入：[64, 34, 25, 12, 22, 11, 90]，目标值：64
输出：True

总结

哈希表搜索是一种高效的搜索算法，它利用哈希函数将元素映射到哈希表中，从而实现 O(1) 时间复杂度的搜索。哈希表搜索适用于需要频繁搜索的场景。

哈希表搜索的核心思想是：利用哈希函数将元素映射到哈希表中，从而实现快速搜索。

掌握哈希表搜索的原理和实现，对于理解哈希表数据结构的搜索操作非常重要。