2841. 几乎唯一子数组的最大和

题目链接：https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/

代码

/**
 * 2841. 几乎唯一子数组的最大和
 * https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/
 */

function maxSum(nums: number[], m: number, k: number): number {
    let res = 0;
    let sum = 0;
    const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        const right = nums[i];
        map.set(right, (map.get(right) || 0) + 1);
        sum += right;
        if (i - k >= 0) {
            const left = nums[i - k];
            const count = map.get(left);
            if (count) {
                map.set(left, count - 1);
                if (count === 1) {
                    map.delete(left);
                }
            }
            sum -= left;
        }
        if (i - k + 1 >= 0 && map.size >= m) {
            res = Math.max(res, sum);
        }
    }
    return res;
}

思路

• 维护长度为 k 的滑动窗口，sum 记录窗口和，map 记录元素频次以计算窗口内不同数字数量。
• 右端进入窗口时更新频次与和；窗口超过 k 时弹出左端元素并维护频次与和。
• 当窗口长度达到 k 且 map.size >= m 时，用当前 sum 更新答案。
• 时间复杂度 $O(n)$，哈希表存储窗口内元素，空间复杂度 $O(k)$。