【Leetcode Daily】2841几乎唯一子数组的最大和

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整数数组，以及两个正整数 m 和 k。要求满足某个条件的子数组的和的最大值。该条件为，该子数组内至少有 m 个不同的数字。

思路分享

• 几乎直接套定长滑动窗口模板解决（【Leetcode Daily】1456定长子串中元音的最大数目），也就是下面陆爻齐的解法。而且个人认为比灵茶山艾府的解法 更易于实现与理解。具体细节放第二点。

• 灵茶山艾府的解法可能更贴近模拟的思路，用 map 记录对应数值数量，当数量为零就删除 map 上对应的数值，统计不同种类数只要调用 map 的 size 函数即可。

• 陆爻齐认为，要统计子数组内不同数字的种类，可以引入一个整形变量来管理，当 map 数字对应的值为零，说明这是新的种类，那么该变量加一；而当对 map 对应数字值减一后，如果 map 的值为零，那么说明子数组中没有该值了，该变量也减一。这样的解法避免了对 map 的 erase 操作。

代码解答（强烈建议自行解答后再看）

• 陆爻齐的解法

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        unordered_map<int, int> rec_num; // 记录窗口内的数值重复情况
        int type_num = 0;
        long long cur_sum = 0;
        long long result = 0;

        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            if (rec_num[nums[i]] == 0) type_num++;
            rec_num[nums[i]]++;

            if (i < k-1) continue; // 初始化窗口

            if (type_num >= m) result = max(cur_sum, result); // 满足几乎唯一的条件

            cur_sum -= nums[i-k+1];
            rec_num[nums[i-k+1]]--;
            if (rec_num[nums[i-k+1]]==0) type_num--;
        }

        return result;
    }
};