LeetCode 2841. 幾乎唯一子陣列的最大和（滑動視窗圖解）

2841. 幾乎唯一子陣列的最大和

題目描述

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

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

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

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

範例 1

輸入：nums = [2,6,7,3,1,7], m = 3, k = 4
輸出：18
解釋：總共有 3 個長度為 k = 4 的幾乎唯一子陣列，分別為 [2, 6, 7, 3]、[6, 7, 3, 1] 和 [7, 3, 1, 7]。
這些子陣列中，和最大的是 [2, 6, 7, 3]，和為 18。

範例 2

輸入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
輸出：23
解釋：總共有 5 個長度為 k = 3 的幾乎唯一子陣列，
和最大的是 [5, 9, 9]，和為 23。

範例 3

輸入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
輸出：0
解釋：不存在長度為 3、且含有至少 3 個互不相同元素的子陣列，所以答案為 0。

限制

• 1 <= nums.length <= 2 * 10^4
• 1 <= m <= k <= nums.length
• 1 <= nums[i] <= 10^9

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

前置知識：滑動視窗

視窗是陣列中由起訖索引定義的一段連續元素。定長視窗每次向右滑一格，就是少一個最左邊的元素、多一個新進來的元素，所以視窗內的總和可以 O(1) 更新，不必每次重算。

思路

題目要的是「長度固定為 k 的視窗，且視窗內不同元素個數 ≥ m，求最大和」，需要同時維護兩個量：

• 視窗總和 s：進來加、出去減。
• 視窗內不同元素的個數：這是難點。

怎麼統計一個陣列有多少不同元素？全丟進雜湊集合，集合大小就是答案。但在滑動視窗裡，元素 x 離開視窗時，要不要從集合刪掉？

• x 是視窗中唯一的一個：刪。
• 視窗裡還有別的 x：不能刪。

要知道 x 在視窗裡還剩幾個，就得記錄出現次數，所以改用雜湊表：key 是元素值，value 是它在視窗中的出現次數。

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

圖解（可互動）

使用範例 1：nums = [2,6,7,3,1,7]，m = 3，k = 4。可以看到雜湊表內容如何隨視窗變化，以及最後一個視窗裡 7 的次數變成 2，但不同元素只有 3 個。

上一步 下一步 重置

nums = [2,6,7,3,1,7]，m = 3，k = 4

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

視窗總和 s0

不同元素 cnt.size()0

目前最大值 ans0

解法（灵茶山艾府）

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        Integer[] a = nums.toArray(Integer[]::new); // 轉成陣列，便於使用

        long ans = 0;
        long s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();

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

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

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

            // 3. 離開視窗
            int out = a[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 最大 2 * 10^4、元素最大 10^9，總和會超過 int。
• cnt.merge(x, 1, Integer::sum) 等價於 cnt[x]++，key 不存在時直接放 1。
• 離開視窗時一定要在次數歸零時 remove，這是這題最容易出錯的地方。

複雜度分析

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