哈希算法题目：宝石与石头

题目描述

给定一个字符串 jewels 代表你拥有的宝石类型，其中每个字符代表一种宝石（jewels 中的所有字符都是唯一的，即无重复字符）。再给定一个字符串 stones 代表你拥有的石头，其中的每个字符代表一种石头。你需要统计在 stones 中有多少颗石头是宝石。换句话说，就是统计 stones 中有多少个字符出现在 jewels 中。

示例：

• 输入：jewels = "aA", stones = "aAAbbbb"
• 输出：3
• 解释：stones 中的字符 'a' 和 'A' 是宝石，其中 'a' 出现 1 次，'A' 出现 2 次，共计 3 次。

解题过程

这道题的核心是快速查找：对于 stones 中的每一个字符，我们需要判断它是否存在于 jewels 中。哈希表（在具体实现中，常用哈希集合）是进行高效成员查找（平均O(1)时间复杂度）的理想数据结构。

步骤 1：理解问题与抽象

1. 输入：两个字符串 jewels 和 stones。
2. 目标：统计 stones 中所有属于 jewels 的字符的出现次数。
3. 关键操作：对于 stones 中的每个字符 c，检查 c 是否在 jewels 的字符集合中。
4. 输出：一个整数，表示满足条件的字符总数。

步骤 2：选择数据结构

• 最直接的方法是使用一个哈希集合（HashSet）。
• 原因：
  • jewels 中的字符是唯一的，天然适合用集合存储。
  • 集合提供了平均 O(1) 时间的成员查询（contains 操作），这比在数组或字符串中直接线性搜索（O(n)）要高效得多，尤其是在 jewels 较长时。

步骤 3：详细算法步骤

1. 初始化一个哈希集合：用于存储所有宝石的类型（即 jewels 中的每个字符）。
2. 遍历 jewels 字符串：将其中每一个字符都添加到这个哈希集合中。
3. 初始化一个计数器：比如 count = 0，用于记录宝石石头的数量。
4. 遍历 stones 字符串：对于 stones 中的每一个字符 c：
   • 查询这个字符 c 是否存在于步骤1创建的哈希集合中。
   • 如果存在，说明 c 是一种宝石，将计数器 count 加 1。
5. 返回计数器 count 的值。

步骤 4：示例推导

以 jewels = "aA", stones = "aAAbbbb" 为例：

1. 创建哈希集合 jewelSet：

   • 遍历 jewels：添加 'a'，添加 'A'。
   • 此时 jewelSet = {'a', 'A'}。

2. 初始化 count = 0。

3. 遍历 stones：

   • 字符 'a'：在集合中吗？是的。count 变为 1。
   • 字符 'A'：在集合中吗？是的。count 变为 2。
   • 字符 'A'：在集合中吗？是的。count 变为 3。
   • 字符 'b'：在集合中吗？否。
   • 字符 'b'：在集合中吗？否。
   • 字符 'b'：在集合中吗？否。
   • 字符 'b'：在集合中吗？否。

4. 最终 count = 3，返回 3。

步骤 5：复杂度分析

• 设 jewels 的长度为 m，stones 的长度为 n。
• 时间复杂度：O(m + n)
  • 构建哈希集合需要遍历 jewels，复杂度 O(m)。
  • 遍历 stones 并检查每个字符是否在集合中，每次检查平均 O(1)，总复杂度 O(n)。
• 空间复杂度：O(m) 或 O(k)`，其中 k 是字符集大小
  • 哈希集合存储了 jewels 中所有不同的字符。由于 jewels 中字符唯一，且字符总数有限（比如 ASCII 字符最多 128/256 个，Unicode 更多但题目通常限定为小写/大写字母），所以空间复杂度可以认为是 O(1) 或 O(m)。

步骤 6：代码实现（概念性伪代码）

function numJewelsInStones(jewels, stones):
    // 步骤1：创建宝石类型集合
    jewelSet = new HashSet()
    for each char c in jewels:
        jewelSet.add(c)
    
    // 步骤2：初始化计数器
    count = 0
    
    // 步骤3：遍历所有石头
    for each char c in stones:
        if jewelSet.contains(c):
            count = count + 1
    
    // 步骤4：返回结果
    return count

总结

这道“宝石与石头”问题是一个经典的哈希集合应用。它清晰地展示了如何利用哈希表（集合）的 O(1) 平均查找时间，将原本可能需要嵌套循环（O(m*n)）的问题，优化为线性时间（O(m+n)）解决。其解题模式——“将待查找的集合预先存入哈希结构，然后对目标进行单次遍历查询”——是解决许多查找类问题的通用高效方法。