題目描述:給整數陣列 nums 和整數 k,回傳所有元素唯一(不含重複)且長度恰好為 k 的子陣列中,元素總和的最大值;若不存在這樣的子陣列,回傳 0。
解題思路:使用固定大小為 k 的滑動視窗,搭配一個 unordered_map 追蹤視窗內各元素的出現次數。維護當前視窗的元素總和 windowSum,以及視窗內重複元素的種數 dupCount(即計數 > 1 的不同值的數量)。
每次右指標向右移動一格,將新元素加入視窗:若該元素出現次數從 1 增至 2,代表視窗剛產生一個重複,dupCount++。當視窗大小超過 k,需移除最左元素:若移除後該元素計數從 2 降至 1,dupCount--;若計數降至 0 則從 map 中刪除。
當視窗大小恰好等於 k 且 dupCount == 0(無任何重複)時,以 windowSum 更新全域答案 maxSum。此方法保證每個元素最多進出視窗各一次,時間複雜度為 O(n)。
時間複雜度:O(n) — 右指標從左到右掃描一遍,每個元素最多進出視窗各一次;雜湊表操作均攤為 O(1)。
空間複雜度:O(k) — 視窗大小固定為 k,雜湊表最多儲存 k 個不同元素。
1. Initialize freq map, windowSum=0, maxSum=0, dupCount=0
2. For right from 0 to n-1:
a. Add nums[right] to windowSum and freq
b. If freq[nums[right]] == 2: dupCount++
c. If window size exceeds k (right >= k):
- Remove nums[right-k] from windowSum and freq
- If freq[nums[right-k]] == 1: dupCount--
- If freq[nums[right-k]] == 0: erase from map
d. If window size == k and dupCount == 0:
- maxSum = max(maxSum, windowSum)
3. Return maxSum暴力列舉 O(n²):對每個起始位置 i,取出長度為 k 的子陣列,用集合檢查是否全為唯一元素,並計算總和。時間 O(nk),空間 O(k)。
排序 + 前綴和 O(n log n):先對每段長度 k 的子陣列建立排序後的版本,以鄰近元素比對是否有重複。但排序破壞了可滑動性,反而更慢。
固定視窗 + set O(n log k):用有序集合 multiset 維護視窗,判斷是否有重複(size < k)。功能正確但常數較大,不如 unordered_map 方案。
nums 是循環陣列(頭尾相連),長度為 k 且元素唯一的子陣列最大和為何?