每个英文字母都被映射到一个数字，如下所示。
如果字符串的字符的映射值的总和可以被字符串的长度整除，则该字符串是 可整除 的。
给定一个字符串 s，请返回 s 的 可整除子串 的数量。
子串 是字符串内的一个连续的非空字符序列。
示例 1：
| Substring | Mapped | Sum | Length | Divisible? |
|---|---|---|---|---|
| a | 1 | 1 | 1 | Yes |
| s | 7 | 7 | 1 | Yes |
| d | 2 | 2 | 1 | Yes |
| f | 3 | 3 | 1 | Yes |
| as | 1, 7 | 8 | 2 | Yes |
| sd | 7, 2 | 9 | 2 | No |
| df | 2, 3 | 5 | 2 | No |
| asd | 1, 7, 2 | 10 | 3 | No |
| sdf | 7, 2, 3 | 12 | 3 | Yes |
| asdf | 1, 7, 2, 3 | 13 | 4 | No |
输入：word = "asdf" 输出：6 解释：上表包含了有关 word 中每个子串的详细信息，我们可以看到其中有 6 个是可整除的。
示例 2:
输入：word = "bdh" 输出：4 解释：4 个可整除的子串是："b"，"d"，"h"，"bdh"。 可以证明 word 中没有其他可整除的子串。
示例 3:
输入：word = "abcd" 输出：6 解释：6 个可整除的子串是："a"，"b"，"c"，"d"，"ab"，"cd"。 可以证明 word 中没有其他可整除的子串。
提示：
1 <= word.length <= 2000word仅包含小写英文字母。
提示 1
Iterate over all substrings in O(n * n).
提示 2
For each substring, try to calculate the sum of the mapped values in O(1).
提示 3
To do the above, use a partial sum array.
解法1: 前缀和 + 哈希表
对于0 <= i < j < n, presum[i] = sum( nums[0...i]) , presum[j] = sum( nums[0...j] ),
presum[j] - presum[i] = sum( nums[i + 1...j]);
对于0 <= i < j < n, ( presum[j] - presum[i] ) % (j - i) == 0，我们枚举 j ，找到符合要求的 i 的个数，然后累加到答案上。
Java版：
class Solution {
public int countDivisibleSubstrings(String word) {
int ans = 0;
int presum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
presum += (c - 'a' + 1) / 3 + 1;
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
if ( (presum - entry.getKey()) % (i - entry.getValue()) == 0 ) {
ans++;
}
}
map.put(presum, i);
}
return ans++;
}
}Python3版：
class Solution:
def countDivisibleSubstrings(self, word: str) -> int:
ans = 0
dic = {0: -1}
presum = 0
for i, c in enumerate(word):
val = (ord(c) - ord('a') + 1) // 3 + 1
presum += val
for k, v in dic.items():
if (presum - k) % (i - v) == 0:
ans += 1
dic[presum] = i
return ans复杂度分析
- 时间复杂度: O(n)，其中 n 为字符串 word 的长度。
- 空间复杂度: O(n)，其中 n 为字符串 word 的长度。哈希表的空间开销为 n 。