題目描述:給定字串 s 和整數 k,回傳長度恰好為 k 的子字串中,母音字母('a', 'e', 'i', 'o', 'u')個數的最大值。
解題思路:使用固定大小的滑動視窗。先建立初始視窗(索引 0 到 k-1),統計其中的母音個數作為 vowelCount,並記錄為當前最大值 maxVowels。接著將視窗向右滑動:每次新加入的字元若為母音則 vowelCount 加一,移出視窗的字元若為母音則 vowelCount 減一,並更新 maxVowels。判斷是否為母音可使用一個含有五個母音的 unordered_set 做 O(1) 查詢,或直接寫一個輔助函式比較字元。特別注意:一旦 vowelCount == k(視窗全為母音),可以立即回傳 k,這是可能的最大值,無需繼續掃描。
時間複雜度:O(n) — 建立初始視窗 O(k),滑動視窗掃描 O(n - k),每次滑動操作 O(1),合計 O(n)。
空間複雜度:O(1) — 輔助 lambda 不佔額外空間,整體只用常數個變數。
1. Define isVowel(c): return true if c is in {a, e, i, o, u}.
2. Initialize vowelCount = count of vowels in s[0..k-1], maxVowels = vowelCount.
3. If maxVowels == k, return k immediately.
4. For right from k to n-1:
a. If s[right] is a vowel, increment vowelCount.
b. If s[right - k] is a vowel, decrement vowelCount.
c. Update maxVowels = max(maxVowels, vowelCount).
d. If maxVowels == k, return k immediately.
5. Return maxVowels.方法一:固定大小滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)。加入提前結束條件(vowelCount == k)可在最好情況下進一步縮短執行時間。
方法二:前綴和統計母音 — 預先建立布林陣列標記每個位置是否為母音,再建立前綴和,對每個視窗用 O(1) 查詢母音數。時間 O(n)、空間 O(n)。邏輯相同但消耗額外記憶體。
方法三:暴力枚舉所有子字串 — 對每個起點 i(共 n - k + 1 個),線性統計 s[i..i+k-1] 中的母音個數。時間 O(n·k)、空間 O(1)。當 k 很大時效率明顯劣於滑動視窗。
isVowel 還是用 unordered_set 更快?在 C++ 中兩者的效能差異體現在哪裡?