題目描述:給定正整數陣列 nums,選擇一個包含唯一(不重複)元素的子陣列並刪除,得分等於該子陣列的元素總和,回傳能獲得的最大得分。
解題思路:本題等價於「找出所有元素不重複的子陣列中,元素總和最大的那一個」。使用可變大小的滑動視窗,搭配 unordered_map 記錄視窗內每個元素的出現次數(或使用 unordered_set 記錄已存在的元素)。右指針 right 持續向右擴展:若 nums[right] 尚未在視窗中出現,則加入視窗並累加 windowSum,更新 maxSum;若已出現,則從左側收縮視窗(left 右移並從 windowSum 扣除、從集合移除),直到重複元素被移出視窗為止,再加入 nums[right]。由於元素為正整數,子陣列越長、包含不重複元素越多,總和越大,因此貪心地讓視窗儘可能大是正確的。最終 maxSum 即為答案。
時間複雜度:O(n) — left 和 right 各最多移動 n 次;unordered_set 的插入、刪除、查詢均為平均 O(1),整體平均 O(n)。最壞情況(雜湊碰撞)為 O(n²),但實務中可忽略。
空間複雜度:O(min(n, v)) — unordered_set 最多存放視窗中的不重複元素,其中 v 為元素值域大小(題目限制 nums[i] ≤ 10⁴),最壞為 O(n)。
1. Initialize left = 0, windowSum = 0, maxSum = 0, window = empty set.
2. For right from 0 to n-1:
a. While nums[right] is in window:
- Remove nums[left] from window.
- Subtract nums[left] from windowSum.
- Increment left.
b. Insert nums[right] into window.
c. Add nums[right] to windowSum.
d. Update maxSum = max(maxSum, windowSum).
3. Return maxSum.方法一:滑動視窗 + unordered_set(最優解) — 如本題解,平均時間 O(n)、空間 O(min(n, v))。直觀且實作簡潔。
方法二:滑動視窗 + 元素最後出現位置 HashMap — 用 unordered_map<int, int> 記錄每個元素最後出現的索引。當遇到重複元素時,直接將 left 跳到 lastIndex[nums[right]] + 1,無需逐步移動 left。時間 O(n)、空間 O(min(n, v))。好處是 left 不需要逐步右移,但須注意跳躍時 windowSum 無法 O(1) 更新,需搭配前綴和才能維持線性。
方法三:前綴和輔助 — 先建立前綴和陣列 prefix,利用雙指針找到所有最大不重複視窗的邊界後,用 prefix[right+1] - prefix[left] 計算總和。時間 O(n)、空間 O(n),適合作為滑動視窗的補充理解。
unordered_set 仍然適用嗎?有什麼替代方案?