LeetCode 2461. 長度為 K 子陣列中的最大和（滑動視窗圖解）

2461. 長度為 K 子陣列中的最大和

題目描述

給你一個整數陣列 nums 和一個整數 k。請你從 nums 中滿足下述條件的全部子陣列中找出最大子陣列和：

• 子陣列的長度是 k，且
• 子陣列中的所有元素各不相同。

回傳滿足題面要求的最大子陣列和。如果不存在子陣列滿足這些條件，回傳 0。

子陣列是陣列中一段連續非空的元素序列。

範例 1

輸入：nums = [1,5,4,2,9,9,9], k = 3
輸出：15
解釋：nums 中長度為 3 的子陣列是：
- [1,5,4] 滿足全部條件，和為 10。
- [5,4,2] 滿足全部條件，和為 11。
- [4,2,9] 滿足全部條件，和為 15。
- [2,9,9] 不滿足，因為元素 9 重複。
- [9,9,9] 不滿足，因為元素 9 重複。
15 是滿足條件的子陣列中的最大和，所以回傳 15。

範例 2

輸入：nums = [4,4,4], k = 3
輸出：0
解釋：唯一的子陣列 [4,4,4] 有重複元素 4，所以不存在滿足條件的子陣列。

限制

• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解為自行補充。

前置知識：滑動視窗與出現次數表

這題和上一篇 LeetCode 2841 幾乎一模一樣，沒看過的話建議先讀那篇。

重點回顧：定長視窗每次右移一格，少一個最左元素、多一個新元素。要統計視窗內有幾種不同元素，需要用雜湊表記錄每個元素的出現次數；元素離開視窗時次數減一，減到 0 才從表中刪除。

思路

「長度為 k 且元素各不相同」等價於：

視窗內不同元素的個數 cnt.size() 恰好等於 k。

因為視窗只有 k 個元素，不同元素個數最多就是 k，等於 k 就代表沒有任何重複。所以只要把 2841 的條件 >= m 改成 == k 即可：

1. 入：x = nums[i] 進入視窗，s += x，cnt[x]++。若 i < k - 1 視窗還沒滿，繼續。
2. 更新：若 cnt.size() == k，用 s 更新答案的最大值。
3. 出：x = nums[i - k + 1] 離開視窗，s -= x，cnt[x]--。若減完是 0，要把 x 從雜湊表刪除，否則 cnt.size() 會算錯。

圖解（可互動）

使用範例 1：nums = [1,5,4,2,9,9,9]，k = 3。注意視窗 [2,9,9] 時 9 的次數是 2，不同元素只有 2 個，小於 k，所以不計入答案。

上一步 下一步 重置

nums = [1,5,4,2,9,9,9]，k = 3

視窗內 入 = 新進入 出 = 剛離開

視窗總和 s0

不同元素 cnt.size()0

目前最大值 ans0

解法（灵茶山艾府）

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long ans = 0;
        long s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            // 1. 進入視窗
            s += nums[i];
            cnt.merge(nums[i], 1, Integer::sum); // cnt[nums[i]]++

            int left = i - k + 1;
            if (left < 0) { // 視窗大小不足 k
                continue;
            }

            // 2. 更新答案
            if (cnt.size() == k) {
                ans = Math.max(ans, s);
            }

            // 3. 離開視窗
            int out = nums[left];
            s -= out;
            int c = cnt.merge(out, -1, Integer::sum); // c = --cnt[out]
            if (c == 0) {
                cnt.remove(out); // 保證 cnt.size() 不計入出現 0 次的元素
            }
        }

        return ans;
    }
}

• s 用 long：k 最大 10^5、元素最大 10^5，總和最大 10^10，超過 int。
• 離開視窗時次數歸零一定要 remove，這是最容易出錯的地方。

複雜度分析

• 時間複雜度：O(n)，其中 n 是 nums 的長度，每個元素進出視窗各一次。
• 空間複雜度：O(k)，雜湊表大小不會超過視窗長度 k。