目標?：刷完靈神專題訓練算法題單

階段目標📌：【算法題單】滑動窗口與雙指針

其他:

今日總結

---

1456. 定長子串中元音的最大數目

跳轉: 1456. 定長子串中元音的最大數目

學習: 靈神：教你解決定長滑窗！

問題:

給你字符串 s 和整數 k 。

請返回字符串 s 中長度為 k 的單個子字符串中可能包含的最大元音字母數。

英文中的 元音字母 為（a, e, i, o, u）。

思路:

定長滑動窗口，先裝入元素，根據題目要求更新，窗口滿員則下次裝入前先退出末尾元素。

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution:def maxVowels(self, s: str, k: int) -> int:ans = vowel = 0for i,c in enumerate(s):if c in "aeiou":vowel += 1if i < k - 1:continueans = max(ans,vowel)if s[i - k + 1] in "aeiou":vowel -= 1return ans

---

643. 子數組最大平均數 I

跳轉: 643. 子數組最大平均數 I

問題:

給你一個由 n 個元素組成的整數數組 nums 和一個整數 k 。

請你找出平均數最大且 長度為 k 的連續子數組，并輸出該最大平均數。

任何誤差小于 10-5 的答案都將被視為正確答案。

思路:

滑動窗口求最大值，題目條件保證 $k<=n$ 。可以先初始化為前k個元素作為初始窗口，然后邊移動邊比較
本質上還是入-更新-出，相當于初始化并更新，然后倒出-裝入-更新。倒出-裝入一步完成

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution:def findMaxAverage(self, nums: List[int], k: int) -> float:maxArgv = temp = sum(nums[:k])for idx in range(0,len(nums)-k):temp += nums[idx+k] - nums[idx]maxArgv = max(maxArgv,temp)return maxArgv / k

---

1343. 大小為 K 且平均值大于等于閾值的子數組數目

跳轉: 1343. 大小為 K 且平均值大于等于閾值的子數組數目

問題:

給你一個整數數組 arr 和兩個整數 k 和 threshold 。

請你返回長度為 k 且平均值大于等于 threshold 的子數組數目。

思路:

這里要求計數，首先threshold與k是整數，商和除數為整數的情況下求被除數不用考慮精度，所以可以直接用threshold * k卡計數條件，初始化-更新，出入-更新滑動窗口即可。

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:ans = 0Bound = threshold * ktemp = sum(arr[:k])if temp >= Bound:ans += 1for idx in range(0,len(arr)-k):temp += arr[idx + k] - arr[idx]if temp >= Bound:ans += 1return ans

---

2090. 半徑為 k 的子數組平均值

跳轉:2090. 半徑為 k 的子數組平均值

問題:

給你一個下標從 0 開始的數組 nums ，數組中有 n 個整數，另給你一個整數 k 。

半徑為 k 的子數組平均值 是指：nums 中一個以下標 i 為 中心 且 半徑 為 k 的子數組中所有元素的平均值，即下標在 i - k 和 i + k 范圍（含 i - k 和 i + k）內所有元素的平均值。如果在下標 i 前或后不足 k 個元素，那么 半徑為 k 的子數組平均值 是 -1 。

構建并返回一個長度為 n 的數組 avgs ，其中 avgs[i] 是以下標 i 為中心的子數組的 半徑為 k 的子數組平均值 。

x 個元素的 平均值 是 x 個元素相加之和除以 x ，此時使用截斷式 整數除法 ，即需要去掉結果的小數部分。

• 例如，四個元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截斷后得到 2 。

思路:

可以看作是窗口大小為 2 * k + 1 的滑動窗口,但更新是在中點處更新，這里采用覆蓋的方式更新值
本質上還是入-更新-出，相當于初始化并更新，然后倒出-裝入-更新。倒出-裝入一步完成

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼:

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:size = k * 2 + 1avgs = [-1 for _ in range(len(nums))]if len(nums) < size:return avgstemp = sum(nums[:size])avgs[k] = temp // sizefor idx in range(0,len(nums) - size):temp += nums[idx + size] - nums[idx]avgs[idx + k + 1] = temp // sizereturn avgs

---

2379. 得到 K 個黑塊的最少涂色次數

跳轉: 2379. 得到 K 個黑塊的最少涂色次數

問題:

給你一個長度為 n 下標從 0 開始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 塊的顏色。字符 'W' 和 'B' 分別表示白色和黑色。

給你一個整數 k ，表示想要 連續 黑色塊的數目。

每一次操作中，你可以選擇一個白色塊將它 涂成 黑色塊。

請你返回至少出現 一次 連續 k 個黑色塊的 最少 操作次數。

思路:

相當于在大小為k的窗口中求白色快最少數量
每一個都需要判斷，不是簡單加和，所以不能偷懶，入-更新-出

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:ans = ktemp = 0for idx,value in enumerate(blocks):if value == 'W':temp += 1if idx < k - 1:continueans = min(temp,ans)if blocks[idx - k + 1] == 'W':temp -= 1return ans

2841. 幾乎唯一子數組的最大和

跳轉: 2841. 幾乎唯一子數組的最大和

問題:

給你一個整數數組 nums 和兩個正整數 m 和 k 。

請你返回 nums 中長度為 k 的 幾乎唯一 子數組的 最大和 ，如果不存在幾乎唯一子數組，請你返回 0 。

如果 nums 的一個子數組有至少 m 個互不相同的元素，我們稱它是 幾乎唯一 子數組。

子數組指的是一個數組中一段連續 非空 的元素序列。

思路:

入-更新-出，但只在滿足不重復元素大于等于m的情況下更新
這里維護字典鍵值對數來判斷不重復元素有多少

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:ans = cnt = 0dict_num = {}for idx,num in enumerate(nums):cnt += numif num in dict_num:dict_num[num] += 1else:dict_num[num] = 1if idx < k - 1:continueif len(dict_num) >= m:ans = max(ans,cnt)temp = nums[idx - k + 1]cnt -= tempif dict_num[temp] == 1:del dict_num[temp]else:dict_num[temp] -= 1return ans

---

總結

練習了定長滑動窗口基礎題目，思路模板為入-更新-出，不一定是簡單的增刪改元素，要考慮有條件的增刪改