宝石与石头 图解题解
这道题到底在问什么
- 输入
- jewels="aA", stones="aAAbbbb"
- 输出
- 3 （a、A、A 是宝石，4 个 b 不是）
- 输入
- jewels="z", stones="ZZ"
- 输出
- 0 （大写 Z 和小写 z 不是一种）
最优解：一步一步想明白
- 3记住口诀：宝石进集合，石头来查询，命中就加一。下面每一帧都在套它。
- 4先把宝石种类登记进集合。现在读到 jewels[0] = "a"，下一帧把它放进去。
- 5"a" 进集合了。集合记的就是「哪些字符算宝石」，以后查一个字符在不在里面非常快。
- 6先把宝石种类登记进集合。现在读到 jewels[1] = "A"，下一帧把它放进去。
- 7"A" 进集合了。集合记的就是「哪些字符算宝石」，以后查一个字符在不在里面非常快。
- 8先把宝石种类登记进集合。现在读到 jewels[2] = "b"，下一帧把它放进去。
- 9"b" 进集合了。集合记的就是「哪些字符算宝石」，以后查一个字符在不在里面非常快。
- 10宝石集合全部建好了，里面是 "a"、"A"、"b" 三种。接下来从头扫 stones，每块石头都来集合里查一下。
- 11扫到 stones[0] = "A"，拿它去宝石集合里问一句：我是宝石吗？
- 12"A" 确实在集合里，是宝石！这块石头标绿，计数加到 1。
- 13扫到 stones[1] = "a"，拿它去宝石集合里问一句：我是宝石吗？
- 14"a" 确实在集合里，是宝石！这块石头标绿，计数加到 2。
- 15扫到 stones[2] = "b"，拿它去宝石集合里问一句：我是宝石吗？
- 16"b" 确实在集合里，是宝石！这块石头标绿，计数加到 3。
- 17扫到 stones[3] = "C"，拿它去宝石集合里问一句：我是宝石吗？
- 18"C" 不在集合里，这块石头不是宝石（注意大小写），标灰跳过，计数还是 3。
- 19扫到 stones[4] = "b"，拿它去宝石集合里问一句：我是宝石吗？
- 20"b" 确实在集合里，是宝石！这块石头标绿，计数加到 4。
- 21扫到 stones[5] = "a"，拿它去宝石集合里问一句：我是宝石吗？
- 22"a" 确实在集合里，是宝石！这块石头标绿，计数加到 5。
- 23扫到 stones[6] = "Z"，拿它去宝石集合里问一句：我是宝石吗？
- 24"Z" 不在集合里，这块石头不是宝石（注意大小写），标灰跳过，计数还是 5。
- 25stones 全部扫完，绿色那 5 块是宝石，灰色的 "C" 和 "Z" 不在集合里。答案就是 5。
⚠️ 容易写错的地方
✗ 错：每块石头都去 jewels 里逐个比对
✓ 对：先把 jewels 放集合，再 O(1) 查询
逐个比对是 O(m×n) 的双重循环，集合查询把它压成 O(m+n)
✗ 错：忽略大小写，把 "a" 和 "A" 当一种
✓ 对：区分大小写，两者是不同的种类
题目明确大小写不同，"z" 和 "Z" 不能算配对
✗ 错：把 stones 放进集合再查 jewels
✓ 对：把唯一的 jewels 放集合，扫 stones 计数
jewels 字符唯一、适合做集合；要统计的是 stones 里有几块命中
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
s = set(jewels)
return sum(c in s for c in stones)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
int s[128] = {0};
for (char c : jewels) {
s[c] = 1;
}
int ans = 0;
for (char c : stones) {
ans += s[c];
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numJewelsInStones(String jewels, String stones) {
int[] s = new int[128];
for (char c : jewels.toCharArray()) {
s[c] = 1;
}
int ans = 0;
for (char c : stones.toCharArray()) {
ans += s[c];
}
return ans;
}
}复杂度
时间
O(m + n)
m 建集合扫 jewels，n 扫 stones，各一遍
空间
O(m)
集合存 jewels 的字符；数组版固定 128 即 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 宝石与石头 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用哈希集合，能不能更省空间？+
能。字符的 ASCII 码不超过 128，开一个长度 128 的数组当集合用：jewels 的字符位置标 1，查询时看对应位置是不是 1。查询同样是 O(1)，而空间是固定的 128，相当于常数。本题参考代码的 C++、Java 版正是这么写的。
这题的套路还能用在哪些题上？+
凡是「判断一批元素是否属于某个固定集合」的问题都适用：比如统计两个字符串有多少公共字符、判断一个数组里的元素是否都在白名单里。核心都是把一边做成集合，另一边扫描查询。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 宝石与石头 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。