我正在研究这个挑战：
给定一个长度为N的包含0个或更多元音的小写字符的字符串，任务是查找给定字符串的所有子字符串中出现的元音数。
示例
Input: str = "abc" Output: 3给定的字符串"；abc"；只包含一个元音="a"。"；abc"；
{"a", "b", "c", "ab", "bc", "abc"}因此，这些字符串中元音的出现次数之和为：
3("a"出现3次)。
如何在O(N)时间复杂性中解决上述问题？
以下是算法中要使用的一些元素：
让我们首先计算一个字符串可以形成多少子字符串(忽略元音计数)：
"a" => {"a"} => 1
"ab" => {"ab", "a", "b"} => 1+2 = 3
"abc" => {"abc", "ab", "bc", "a", "b", "c"} => 1+2+3 = 6
"abcd" => {"abcd", "abc", "bcd", "ab", "bc", "cd", "a", "b", "c", "d"} => 1+2+3+4 = 10
...
图案为1+2+3+…+，其中是字符串的长度，为(+1)/2
现在让我们取一个只有一个元音的字符串："klmnopqrst"；。然后，答案包括计算有这个元音的子串的数量。
我们知道总共有10(10+1)/2=55个子串，但其中许多计数的子串没有元音。没有"0"的减法；klmn"；有元音。有4(4+1)/2＝10个这样的减法。也没有"0"的减法；pqrst"；有元音。有5(5+1)/2=15个这样的子串。所有其他子串都有元音。所以我们可以做减法。。。输出应该是55-10-15=30。
因此，一般原则是：对于输入中的每个元音，通过计算元音的左侧和右侧的子串数量，确定不包含该元音的子串有多少。这为我们提供了关于包含该元音的子串数量的线索——通过从子串总数中减去非大小写。
如果我们对每个元音都这样做，我们就会计算出所有子串中元音的总出现次数。
这是用伪代码表示的算法：
function occurrence(str):
n := length(str)
total := 0
allcount := n * (n + 1) // 2
for i := 1 to n:
if str[i] is a vowel:
total = total + allcount - (i - 1) * i / 2 - (n - 1 - i) * (n - i) / 2
return total
注意：正如伪代码中常见的那样，i是位置(从1开始)，而不是基于零的索引。
(以防trincot的答案不够。)
每个元音出现在(l + 1) * (r + 1)子串中，其中l是元音左侧的字符数，r是元音右侧的字符数。
Example 1:
"abc"
'a': (0 + 1) * (2 + 1) = 3
Total: 3
Example 2:
"ae"
'a': (0 + 1) * (1 + 1) = 2
'e': (1 + 1) * (0 + 1) = 2
Total: 4