1. 问题引入从“宝石与石头”到哈希集合的初体验如果你刚开始接触LeetCode或者正在用Python刷题来巩固基础那么第771题“Jewels and Stones”绝对是一个完美的起点。这道题在力扣的题库里被标记为“简单”但千万别小看它。它就像是你编程工具箱里的第一把螺丝刀看起来简单却能帮你拧开很多复杂问题的大门。题目描述非常直白给你两个字符串jewels代表宝石的类型stones代表你拥有的石头。你需要统计在stones字符串中有多少个字符是出现在jewels字符串中的。简单来说就是在你的石头堆里找出哪些是宝石并数一数个数。我第一次看到这个题目时觉得这太简单了不就是两层循环遍历比较吗但正是这种“简单”的错觉让我后来在面试中栽过跟头。面试官追问“如果jewels和stones的长度都非常大比如各有一百万个字符你的算法效率如何” 我当时的朴素解法瞬间就暴露了性能瓶颈。这道题的核心远不止是完成功能而是引导你思考一个在编程中至关重要的问题如何高效地进行存在性判断。而解决这个问题的钥匙就是“哈希集合”。在Python中它对应的数据结构是set。通过这道题你会深刻理解为什么以及何时该用set而不是无脑地用list。这不仅是解一道题更是建立一种正确的、高效的编程思维定式。2. 暴力解法剖析为什么两层循环是“性能杀手”我们先从最直观的解法开始这也是很多初学者包括当年的我会第一时间想到的方法暴力枚举。2.1 暴力解法的实现代码class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: count 0 for stone in stones: for jewel in jewels: if stone jewel: count 1 break # 找到即跳出内层循环 return count这段代码的逻辑清晰得像一面镜子对于stones里的每一块石头外层循环我们都去jewels这个宝石列表里从头到尾比对一遍内层循环。如果找到了相同的字符计数器加一并且因为一块石头只可能是一种宝石找到了就不用继续比了所以用break跳出内层循环。2.2 时间复杂度分析与性能陷阱我们来算一笔账。假设jewels的长度为mstones的长度为n。在最坏的情况下比如没有一块石头是宝石或者最后一块石头才是宝石对于stones中的每一个字符我们都需要遍历完整个jewels字符串。因此总的比较次数是n * m。在算法领域我们用大O表示法来描述这种增长关系即时间复杂度为O(m * n)。当m和n都很小时比如几十上百这个速度人类感知不到差异。但正如我面试时遇到的问题当数据规模上升到十万、百万级别时O(m*n)的复杂度是灾难性的。计算量会呈平方级增长程序可能会运行数秒甚至更久这在算法竞赛或线上服务中是绝对不允许的。这里有一个常见的误解我用了break不是应该快很多吗break确实能在找到匹配后提前结束内层循环但这改变不了时间复杂度最坏情况仍然是O(m*n)的事实。它只是一个常数级别的优化并没有改变算法随数据规模增长的本质。这就好比你要在一本无序的电话簿里找一个人最坏情况下你还是得翻遍每一页虽然中途找到可以停下但改变不了“可能需要翻完整本”这个糟糕的流程设计。3. 哈希集合解法将查找时间降至常数级既然暴力解法的瓶颈在于对于每一块石头都需要在宝石列表中“线性扫描”查找那么优化的核心就是让这个查找动作变得飞快。哈希表Hash Table正是为此而生的数据结构在Python中它的一个典型应用就是集合set。3.1 哈希集合的核心思想与Python实现set是一个无序的不重复元素集。它的魔法在于基于哈希表实现使得判断一个元素是否存在于集合中的操作其平均时间复杂度是O(1)即常数时间。这意味着无论这个集合里有10个元素还是10万个元素检查“某个元素在不在里面”所花的时间几乎是一样的。解题思路立刻变得清晰预处理宝石列表将字符串jewels转换成集合jewel_set。这个操作需要遍历jewels一次时间复杂度O(m)。高效统计石头遍历字符串stones对于每一块石头只需用in操作符判断它是否在jewel_set中。这个判断是O(1)的。遍历stones是O(n)。汇总结果将在集合中的石头计数。转换后的代码如下class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: jewel_set set(jewels) # 关键步骤构建哈希集合 count 0 for stone in stones: if stone in jewel_set: # O(1)时间复杂度的查找 count 1 return count3.2 复杂度对比与质的飞跃让我们重新计算复杂度时间复杂度构建集合O(m) 遍历石头O(n)O(m n)。从乘法关系O(m*n)降到了加法关系O(mn)这是一个质的飞跃。当m和n都是100万时暴力解法可能需要万亿次操作而哈希集合解法只需要大约200万次操作。空间复杂度我们额外使用了一个集合来存储宝石类型其大小最多为m如果jewels中字符全不重复。因此空间复杂度是O(m)。这是典型的“以空间换时间”策略在绝大多数情况下这点额外的内存开销换取巨大的时间性能提升是完全值得的。你可以自己做一个实验用timeit模块测试两种解法在长字符串下的性能差异结果会非常直观。哈希集合解法的优势在处理大规模数据时是碾压性的。4. 一行代码的优雅解法Pythonic思维的体现对于Python开发者来说追求代码的简洁与优雅是一种习惯。利用Python强大的内置函数和生成器表达式我们可以将上面的解法浓缩成一行代码class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: return sum(stone in set(jewels) for stone in stones)这行代码做了以下几件事set(jewels)同样先将宝石字符串转换为集合。(stone in set(jewels) for stone in stones)这是一个生成器表达式。它会遍历stones中的每个字符并产生一个布尔值序列True或False表示该石头是否是宝石。sum(...)在Python中布尔值True和False在参与算术运算时会被当作1和0处理。sum函数将这个由1和0组成的序列加起来自然就得到了宝石的总数。注意这种写法虽然极其简洁但在某些讨论中需要注意性能细节。这里set(jewels)在生成器表达式内部但因为它只被创建一次生成器表达式会先计算其可迭代对象所以时间复杂度依然是O(mn)。不过更严谨且高效的写法是将set(jewels)赋值给一个变量避免任何潜在的误解或重复构造尽管解释器通常会优化。不过在这种短小的表达式中可读性和简洁性成为了更优先的考量这也是Pythonic哲学的一部分。5. 深入拓展从本题到更广泛的哈希表应用场景解完这道题绝不能止步于此。LeetCode 771的真正价值在于它为你打开了一扇门让你看到了哈希表在Python中主要是dict和set在解决一大类问题时的威力。这类问题的核心模式可以概括为需要频繁、快速地检查某个元素是否存在或者需要建立元素到其他信息的映射关系。5.1 同类问题举一反三掌握了Jewels and Stones的思维下面这些题目你都能触类旁通LeetCode 1. Two Sum两数之和这是哈希表字典最经典的入门题。核心是在遍历数组时用字典记录每个数字的补数target - num及其索引。当遇到一个数字它的值已经在字典中作为键存在时就找到了答案。这本质上是将“寻找满足条件的另一个数”的查找操作从遍历优化成了O(1)的字典查找。LeetCode 349. Intersection of Two Arrays两个数组的交集几乎和本题一模一样求两个数组的交集。直接使用集合的交集操作或者将一个数组转为集合然后遍历另一个数组判断是否存在。LeetCode 387. First Unique Character in a String字符串中的第一个唯一字符通常需要两遍遍历。第一遍用字典统计每个字符出现的次数O(n)第二遍遍历字符串找到第一个计数为1的字符O(n)。如果不用哈希表统计查找过程会变得低效。5.2 哈希表在Python中的选择setvsdict本题我们用了set因为它只关心“存在与否”。但在更多场景下我们需要关联更多的信息这时就要用到dict。set存储唯一的、不可变的对象集合。只支持成员检测、交集并集等集合操作。适用于去重或单纯的存在性检查。dict存储键值对key-value pairs。键必须是不可变类型如字符串、数字、元组值可以是任意对象。适用于需要根据键快速检索关联值的场景如统计频率、缓存结果、建立映射关系。例如在“两数之和”中我们需要存储的是“数值”和“它的索引”的映射所以必须用dict。而在“宝石与石头”中我们只需要知道宝石类型有哪些不需要知道其他信息所以set就足够了。5.3 一个综合性的实战变种假设题目稍微变化一下jewels不再是一个简单的字符串而是一个列表里面每个元素是一个宝石对象对象有type类型如‘R’ ‘S’和value价值整数属性。stones是一个字符串。现在需要计算你拥有的所有宝石的总价值。这时set就不够用了因为我们需要根据石头类型字符快速查到对应的价值。解决方案是使用字典def total_jewel_value(jewels_list, stones): # 构建一个从宝石类型到价值的映射字典 jewel_value_map {} for jewel in jewels_list: jewel_value_map[jewel.type] jewel.value total_value 0 for stone in stones: # 如果石头类型在字典中累加其价值 if stone in jewel_value_map: total_value jewel_value_map[stone] return total_value这个变种清晰地展示了何时该从set升级到dict当你需要存储和查找与键相关联的额外信息时。6. 常见误区与避坑指南在实际编码和面试中围绕这道题和哈希表的使用有一些高频的“坑点”。6.1 误区一忽视字符集与输入范围题目虽简单但一个良好的习惯是考虑输入范围。题目说明jewels和stones仅由英文字母组成。这意味着字母区分大小写。‘a‘和’A‘是不同的宝石类型。总字符种类是有限的52种。这带来一个有趣的点当jewels种类很少时比如只有几种暴力法和哈希法在实际运行时间上可能相差不大因为常数项很小。但算法思维不应依赖于这种特定数据。我们学习的是通用、高效的解法它应该在任何规模、任何分布的数据上都表现良好。6.2 误区二在循环中重复构造集合这是一个初学者和追求“一行代码”时容易犯的错误# 低效写法 def numJewelsInStones(jewels, stones): count 0 for stone in stones: if stone in set(jewels): # 错误在每次循环中都创建新的集合 count 1 return count这段代码的时间复杂度退化成了O(n * m)因为set(jewels)在每次循环中都被重新创建。一定要记住将不变的、可复用的计算结果如这里的jewel_set提到循环外部这是一个重要的性能优化原则。6.3 误区三过度优化与可读性权衡我们讨论了一行代码的写法。但在团队合作或大型项目中有时需要权衡简洁性与可读性。对于刚入门的同事来说下面这种展开的写法可能更友好意图更清晰def numJewelsInStones(jewels, stones): jewel_types set(jewels) jewel_count 0 for stone in stones: if stone in jewel_types: jewel_count 1 return jewel_count变量名jewel_types比s更能表达其含义循环体也清晰明了。在追求“Pythonic”的同时永远不要牺牲代码的清晰度和可维护性。尤其是在面试中先写出清晰正确的版本再视情况优化往往是更稳妥的策略。7. 测试用例设计与边界条件思考写出代码只是第一步验证其正确性同样重要。自己设计测试用例是一个优秀程序员必备的习惯。针对本题我们可以考虑以下几类基础功能测试输入jewels “aA“ stones ”aAAbbbb“预期输出3a出现1次A出现2次目的验证基本计数功能。边界条件测试空字符串jewels ““ stones ”abc“- 输出0jewels “a“ stones ””- 输出0jewels ““ stones ””- 输出0无匹配jewels “z“ stones ”ZZZ“- 输出0全匹配jewels “abc“ stones ”cbaabc“- 输出6性能暗示测试构造很长的jewels和stones字符串例如各10万个字符。虽然无法手动验证结果但可以运行并感受两种解法的时间差异。用暴力解法可能会卡住而哈希集合解法瞬间完成。养成在提交前用多种用例测试自己代码的习惯能极大提高一次通过率并锻炼出严密的思维。8. 总结与思维升华回顾LeetCode 771 “Jewels and Stones”的整个解题过程它绝不仅仅是一道简单的计数题。它是一次经典的算法思维训练从暴力到优化我们经历了最直观的O(m*n)解法并分析了其性能瓶颈。这是算法学习的必经之路——先解决问题再优化问题。认识核心数据结构我们引入了哈希集合set理解了其O(1)查找时间的原理并将算法复杂度优化至O(mn)。这是“以空间换时间”策略的入门级示范。掌握Python工具我们运用了set、in操作符、生成器表达式和sum函数领略了Python的简洁与高效。建立问题模式我们识别出了“频繁存在性检查”这一模式并将其与哈希表这一数据结构关联起来为解决“两数之和”、“数组交集”等更多问题打下了基础。培养工程习惯我们讨论了代码风格、性能陷阱、测试用例和边界条件这些都是编写健壮、可维护代码的重要组成部分。这道题像一颗种子它种下的是一种思想当你的程序需要在数据集中反复查找时第一个应该想到的就是哈希表。在后续遇到更复杂的问题比如缓存LRU Cache、索引、去重、关系映射时你会发现哈希表及其变种如defaultdictCounter是你武器库中最常被使用的利器之一。所以下次再看到“简单”的题目不妨多想一想它背后试图教给你的究竟是什么。