LeetCode 题解工作台
最大质数子字符串之和
给定一个字符串 s ，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。 返回这些质数的 总和 ，如果少于 3 个不同的质数，则返回 所有 不同质数的和。 质数是大于 1 且只有两个因数的自然数：1和它本身。 子字符串 是字符串中的一个连续字符序列。 注意： 每个质数即使出现在 多个 子字符…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
我们可以枚举所有的子字符串，然后判断它们是否是质数。由于题目要求我们返回最大的 3 个不同质数的和，因此我们可以使用一个哈希表来存储所有的质数。 在遍历完所有的子字符串后，我们将哈希表中的质数按从小到大的顺序排序，然后取出最大的 3 个质数进行求和。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给定一个字符串 s，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。
返回这些质数的 总和 ，如果少于 3 个不同的质数，则返回 所有 不同质数的和。
质数是大于 1 且只有两个因数的自然数：1和它本身。
子字符串 是字符串中的一个连续字符序列。
注意：每个质数即使出现在 多个 子字符串中，也只能计算 一次 。此外，将子字符串转换为整数时，忽略任何前导零。
示例 1：
输入： s = "12234"
输出： 1469
解释：
- 由
"12234"的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。 - 最大的 3 个质数是 1223、223 和 23。它们的和是 1469。
示例 2：
输入： s = "111"
输出： 11
解释：
- 由
"111"的子字符串形成的不同质数是 11。 - 由于只有一个质数，所以结果是 11。
提示：
1 <= s.length <= 10s仅由数字组成。
解题思路
方法一：枚举 + 哈希表
我们可以枚举所有的子字符串，然后判断它们是否是质数。由于题目要求我们返回最大的 3 个不同质数的和，因此我们可以使用一个哈希表来存储所有的质数。
在遍历完所有的子字符串后，我们将哈希表中的质数按从小到大的顺序排序，然后取出最大的 3 个质数进行求和。
如果哈希表中质数的数量小于 3，则返回所有质数的和。
时间复杂度 ，空间复杂度 ，其中 为字符串的长度，而 为字符串中最大的子字符串的值。
class Solution:
def sumOfLargestPrimes(self, s: str) -> int:
def is_prime(x: int) -> bool:
if x < 2:
return False
return all(x % i for i in range(2, int(sqrt(x)) + 1))
st = set()
n = len(s)
for i in range(n):
x = 0
for j in range(i, n):
x = x * 10 + int(s[j])
if is_prime(x):
st.add(x)
return sum(sorted(st)[-3:])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is roughly O(n^3) due to generating all substrings and checking each for primality. Space complexity is O(k) where k is the number of unique prime numbers stored in the hash table. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on hash table usage to prevent duplicate prime counting from overlapping substrings.
- question_mark
Expect efficient math checks for primality due to potential large numeric substrings.
- question_mark
Clarify handling of leading zeros and small input strings.
常见陷阱
外企场景- error
Forgetting to ignore leading zeros when converting substrings to integers.
- error
Counting the same prime multiple times if it appears in different substrings.
- error
Inefficient primality checks causing timeouts on larger numeric substrings.
进阶变体
外企场景- arrow_right_alt
Return the sum of the k largest unique prime substrings instead of three.
- arrow_right_alt
Count primes formed only by substrings of a fixed length.
- arrow_right_alt
Compute the product instead of the sum of the largest prime substrings.