哈希算法题目：宝石与石头 题目描述 给定一个字符串 jewels 代表宝石的类型，以及一个字符串 stones 代表你拥有的石头。 stones 中的每个字符代表了一种你拥有的石头的类型。你想知道你拥有的石头中有多少是宝石。 字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。 示例 1: 输入: jewels = "aA", stones = "aAAbbbb" 输出: 3 解释: 字符串 stones 中有三个 'a' 或 'A' 的字符，它们都是宝石。 示例 2: 输入: jewels = "z", stones = "ZZ" 输出: 0 解释: 大小写敏感， stones 中的 'Z' 和 'z' 不同，所以没有宝石。 解题过程 问题分析 目标：统计字符串 stones 中有多少个字符出现在字符串 jewels 中。 核心操作：对于 stones 中的每一个字符，我们需要快速判断它是否存在于 jewels 中。 关键点：字母区分大小写。 选择数据结构 最直接的思路是使用两层循环：遍历 stones 中的每个字符，对于每个字符，再遍历一遍 jewels 看是否存在。这种方法的时间复杂度是 O(n* m)，其中 n 是 stones 的长度，m 是 jewels 的长度。当字符串较长时，效率较低。 优化思路：为了快速判断一个元素是否存在，哈希表（在 Python 中常用集合 set ）是最佳选择。我们可以先将所有宝石类型存入一个集合，这个集合的查找操作时间复杂度为 O(1)。 算法步骤 步骤一：构建宝石集合 创建一个哈希集合 jewel_set ，遍历字符串 jewels ，将其中的每一个字符添加到集合中。 为什么用集合？集合保证了元素的唯一性，并且提供了常数时间复杂度的成员检查（ in 操作）。 例如，对于 jewels = "aA" ， jewel_set 的内容是 {'a', 'A'} 。 步骤二：遍历并统计石头 初始化一个计数器 count ，初始值为 0。 遍历字符串 stones 中的每一个字符： 对于当前字符 stone ，检查它是否存在于我们刚刚创建的集合 jewel_set 中。 如果存在（ if stone in jewel_set ），说明这是一颗宝石，将计数器 count 加 1。 如果不存在，则不做任何操作，继续检查下一个字符。 步骤三：返回结果 遍历完 stones 中的所有字符后，计数器 count 的值就是宝石的数量，将其作为结果返回。 复杂度分析 时间复杂度：O(m + n) 构建宝石集合需要遍历 jewels 字符串，时间复杂度为 O(m)，m 是 jewels 的长度。 遍历并统计 stones 需要 O(n) 的时间，n 是 stones 的长度。 总时间复杂度为 O(m + n)，这比最初的 O(m* n) 要高效得多。 空间复杂度：O(m) 主要是用于存储宝石集合 jewel_set 所消耗的空间，在最坏情况下（所有宝石字符都不同），需要 O(m) 的额外空间。 总结 这道题展示了哈希集合在快速查找方面的经典应用。通过将需要判断的“目标集合”（宝石）预先存入哈希表，我们将原本需要线性扫描的查找操作优化成了常数时间，从而显著提升了整个算法的效率。解决此类“判断存在性”的问题，应优先考虑使用哈希表（或集合）来优化性能。