企业官网建设流程全解析

LeetCode-Go 题解 771. Jewels and Stones：宝石与石头计数问题

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode-Go 仓库中 771. Jewels and Stones 题解目录 展开，完整讲解「宝石与石头」这道哈希表入门题的题意、约束与两类 Go 实现思路。读完本文，你将掌握字符串单字符逐一遍历、strings.Contains子串判定与map[rune]bool查表两种解法的时间/空间复杂度差异，并能直接运行仓库内置的单测验证结果。

一、题目描述

给定字符串J表示石头的类型中哪些属于宝石（Jewels），字符串S表示你拥有的石头（Stones）。S中每一个字符代表一种你拥有的石头类型，需要统计：你拥有的石头中有多少颗同时也是宝石。

关键约束如下：

• J中的字母互不重复；
• J与S中的所有字符均为字母；
• 字母区分大小写，例如"a"与"A"被视为不同类型的石头；
• S与J的长度至多为 50。

示例 1：

Input: J = "aA", S = "aAAbbbb" Output: 3

S中有 1 个a与 2 个A属于宝石集合{a, A}，共 3 颗。

示例 2：

Input: J = "z", S = "ZZ" Output: 0

S中只有大写Z，与宝石类型z不匹配（大小写敏感），结果为 0。

二、题目大意

给定字符串J代表石头中宝石的类型，字符串S代表你拥有的石头。S中每个字符代表一种你拥有的石头类型，统计你拥有的石头中有多少颗是宝石。J中的字母不重复，J与S中所有字符都是字母，且字母区分大小写，因此"a"与"A"是不同类型的石头。

三、解题思路

这是一道典型的哈希表入门题，核心任务是在S中统计落在宝石集合J内的字符个数。仓库中提供了两种解法，均可在 771. Jewels and Stones.go 中查看完整源码。

解法一：strings.Contains 逐字符判定

// 解法一 func numJewelsInStones(J string, S string) int { count := 0 for i := range S { if strings.Contains(J, string(S[i])) { count++ } } return count }

该实现直接利用标准库strings.Contains：遍历S的每一个字节，将S[i]转为字符串后判断其是否作为子串出现在J中。

• 由于J中字母互不重复且长度不超过 50，Contains内部的字节级扫描开销很小，写法最简洁；
• 时间复杂度为 O(|S| × |J|)，空间复杂度 O(1)；
• 注意string(S[i])将单个字节转换为字符串再参与子串匹配，这保证了大小写敏感的行为与题目要求一致。

解法二：map 缓存宝石类型

// 解法二 func numJewelsInStones1(J string, S string) int { cache, result := make(map[rune]bool), 0 for _, r := range J { cache[r] = true } for _, r := range S { if _, ok := cache[r]; ok { result++ } } return result }

该实现先遍历J，用map[rune]bool记录所有宝石类型，再遍历S，通过一次 map 查找判断当前石头是否为宝石。

• 两次遍历均为线性，时间复杂度 O(|J| + |S|)，空间复杂度 O(|J|)；
• 用rune而非byte作为 key，对 ASCII 字母场景二者等价，但语义上更贴近"字符类型"的定义；
• 当字符串长度接近题目上限 50 时，map 版本的查找优势开始显现，是更可扩展的实现。

两种解法对比

四、测试用例验证

仓库为本题配套了单测文件 771. Jewels and Stones_test.go，覆盖了题目给出的两个官方示例：

qs := []question771{ { para771{"aA", "aAAbbbb"}, ans771{3}, }, { para771{"z", "ZZ"}, ans771{0}, }, }

测试函数Test_Problem771对每个用例分别调用numJewelsInStones与numJewelsInStones1，验证两种解法的输出与预期答案一致。其中第一个用例同时覆盖了"大小写敏感"这一关键约束（a与A都被统计，而b不计入）。

运行方式：进入仓库根目录后执行

go test -v -run Test_Problem771 ./leetcode/0771.Jewels-and-Stones/

仓库根目录下的 gotest.sh 脚本则演示了覆盖全仓库所有题解的标准测试命令（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），运行环境以 go.mod 声明的 Go 1.19 及以上版本为前提。

五、小结

771 题虽然难度为 Easy，但完整覆盖了哈希表解题的典型套路：将"集合判定"问题转化为查表问题，用空间换时间。解法一适合快速作答，解法二则体现了可扩展的工程化写法。配合仓库中的单测，读者可以随时回归验证，并以此为模板理解后续更多哈希表类题目（如 217. Contains Duplicate、242. Valid Anagram）的解题思路。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go