难度: Medium
Submission
运行时间: 109 ms
内存: 16.4 MB
class Solution:
def countDivisibleSubstrings(self, word: str) -> int:
mapping = dict()
for i, c in enumerate(string.ascii_lowercase):
mapping[c] = (i + 1) // 3 + 1
# print(mapping)
nums = [mapping[w] for w in word]
result = 0
for mean in range(1, 10):
pre_sum = 0
count = {0: 1}
diff = [d - mean for d in nums]
for it in diff:
pre_sum += it
if pre_sum in count:
result += count[pre_sum]
count[pre_sum] += 1
else:
count[pre_sum] = 1
# print(count)
return result
def countDivisibleSubstrings2(self, word: str) -> int:
mapping = dict()
for i, c in enumerate(string.ascii_lowercase):
mapping[c] = (i + 1) // 3 + 1
# print(mapping)
result = 0
n = len(word)
for i in range(n):
t = 0
for j in range(i, n):
t += mapping[word[j]]
if t % (j - i + 1) == 0:
result += 1
return result
Explain
题解中包含两种方法。第一种方法使用了前缀和和哈希表的技术，将问题转化为求和为特定值的子数组数量。具体来说，对于每个可能的均值mean从1到9，计算数组中每个元素减去mean的结果，然后使用前缀和和哈希表来找出和为0的子数组数量。第二种方法是通过枚举所有可能的子串，对每个子串计算其元素映射值的总和，并检查这个总和是否可以被子串的长度整除，是则计数增加。
时间复杂度: 第一种方法O(n)，第二种方法O(n^2)
空间复杂度: 第一种方法O(n)，第二种方法O(1)
class Solution:
def countDivisibleSubstrings(self, word: str) -> int:
mapping = dict()
for i, c in enumerate(string.ascii_lowercase):
mapping[c] = (i + 1) // 3 + 1
nums = [mapping[w] for w in word]
result = 0
for mean in range(1, 10):
pre_sum = 0
count = {0: 1}
diff = [d - mean for d in nums]
for it in diff:
pre_sum += it
if pre_sum in count:
result += count[pre_sum]
count[pre_sum] += 1
else:
count[pre_sum] = 1
return result
def countDivisibleSubstrings2(self, word: str) -> int:
mapping = dict()
for i, c in enumerate(string.ascii_lowercase):
mapping[c] = (i + 1) // 3 + 1
result = 0
n = len(word)
for i in range(n):
t = 0
for j in range(i, n):
t += mapping[word[j]]
if t % (j - i + 1) == 0:
result += 1
return result
Explore
这里的范围1到9是基于字母到数字的映射规则确定的。在映射中，每个字母被映射到一个特定的值，这个值是字母的位置除以3再加1。因为英文字母共有26个，最高的映射值为(26 / 3) + 1，即约为9。因此，均值mean的范围设定为1到9，以覆盖所有可能的映射值，确保算法的全面性和正确性。
在第一种方法中，先计算每个元素与均值mean的差值，然后对这些差值序列计算前缀和。使用哈希表来记录各个前缀和出现的次数。当我们在计算过程中再次遇到同一个前缀和值时，这意味着从上一次该前缀和出现的位置到当前位置的子数组的和为0（因为两个相同的前缀和之间的差分为零）。通过查询哈希表中该前缀和的出现次数，我们可以直接得知有多少个这样的子数组。每次遇到已存在的前缀和时，从哈希表中获取计数并将其加到结果中，同时更新哈希表中该前缀和的次数。
是的，第二种方法的效率确实较低，特别是对于较长的字符串。这种方法的时间复杂度是O(n^3)，因为需要枚举每个可能的子串（O(n^2)），并且对于每个子串，计算其所有元素的映射值的总和（O(n)）。随着字符串长度的增加，计算量急剧增加，导致效率低下。这种方法在实际应用中可能不适用于处理大规模数据或需要高效率的场景。
在前缀和方法中，哈希表记录的是每个前缀和值出现的次数。当我们在计算过程中遇到一个已存在于哈希表中的前缀和时，这表示从之前某个位置到当前位置的子数组的和为0（差分数组中的和为0）。哈希表中该前缀和的计数表明之前已有多少个子数组的结束位置可以与当前位置形成和为0的子数组。因此，可以直接使用这个计数增加到结果中，因为它代表了以当前位置为结束点的符合条件的子数组数量。