題目鏈接：https://leetcode-cn.com/problems/vowels-of-all-substrings/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

給你一個字符串 word ，返回 word 的所有子字符串中 元音的總數 ，元音是指 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。

子字符串 是字符串中一個連續（非空）的字符序列。

注意：由于對 word 長度的限制比較寬松，答案可能超過有符號 32 位整數的范圍。計算時需當心。

示例 1：
輸入：word = “aba”
輸出：6
解釋：
所有子字符串是：“a”、“ab”、“aba”、“b”、“ba” 和 “a” 。
“b” 中有 0 個元音
“a”、“ab”、“ba” 和 “a” 每個都有 1 個元音
“aba” 中有 2 個元音
因此，元音總數 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。

示例 2：
輸入：word = “abc”
輸出：3
解釋：
所有子字符串是：“a”、“ab”、“abc”、“b”、“bc” 和 “c” 。
“a”、“ab” 和 “abc” 每個都有 1 個元音
“b”、“bc” 和 “c” 每個都有 0 個元音
因此，元音總數 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。

示例 3：
輸入：word = “ltcd”
輸出：0
解釋：“ltcd” 的子字符串均不含元音。

示例 4：
輸入：word = “noosabasboosa”
輸出：237
解釋：所有子字符串中共有 237 個元音。

提示：
1 <= word.length <= 105
word 由小寫英文字母組成

---

思路一：數學規律

以abcde字符串為例，每個部分出現的次數可以拆分成：

• a出現的次數：$(5?1)+((5?0)?0)+1$;
• b出現的次數：$(5?2)+((5?1)?1)+1$;
• c出現的次數：$(5?3)+((5?2)?2)+1$;
• d出現的次數：$(5?4)+((5?3)?3)+1$;
• e出現的次數：$(5?5)+((5?4)?4)+1$;

編寫代碼即可：

class Solution { private:const long long MAX_LEN = 100005;long long arr[100005] = {0}; public:long long countVowels(string word) {long long res = 0;long long len = word.length();// 第一部分for(int i = 0; i < len; i++) {arr[i] += len-1-i;}for(int i = 0; i < len; i++) {arr[i] += (len - i) * (i); // 第二部分arr[i] += 1; // 第三部分}for(int i = 0; i < len; i++) {if(word[i] == 'a' || word[i] == 'e'|| word[i] == 'i'|| word[i] == 'o'|| word[i] == 'u') {res += arr[i];}}return res;} };

總結

以上是生活随笔為你收集整理的24行代码-Leecode 2063. 所有子字符串中的元音——Leecode周赛系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。