【Leetcode Daily】2461长度为K子数组中的最大和

题目浅析

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

• 简单地说，就是给一个整型数组和一个数字 K，要求一个长度为 K 且内部数字各不相同的子数组之和的最大值。

思路分享

• 就是上一题（【Leetcode Daily】2841几乎唯一子数组的最大和）把不相同数字固定为 k 的改版，直接用模板（【Leetcode Daily】1456定长子串中元音的最大数目）写过，也就是下面的陆爻齐解法。

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

• 陆爻齐解法

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> rec_num;
        long long res = 0;
        long long cur_sum = 0;
        int type_count = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            rec_num[nums[i]]++;
            if (rec_num[nums[i]]==1) {
                type_count++;
            }

            if (i < k-1) continue;

            if (type_count == k && cur_sum > res) {
                res = cur_sum;
            }

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

        return res;
    }
};