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

本文主要是介绍Leetcode2841. 几乎唯一子数组的最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：2841. 几乎唯一子数组的最大和

解法1：滑动窗口

看到「长度固定的子数组」就要想到滑动窗口。

用一个哈希表 mp 维护窗口内的元素出现次数，当窗口内的 mp.size()>=m 时，更新子数组最大和。

代码：

/** @lc app=leetcode.cn id=2841 lang=cpp** [2841] 几乎唯一子数组的最大和*/// @lc code=start// 滑动窗口class Solution
{
public:long long maxSum(vector<int> &nums, int m, int k){// 特判if (nums.empty() || m > k)return 0LL;long long max_sum = 0LL;vector<int> window;unordered_map<int, int> mp;for (int i = 0; i < nums.size(); i++){window.push_back(nums[i]);mp[nums[i]]++;while (window.size() > k){mp[*window.begin()]--;if (mp[*window.begin()] == 0)mp.erase(*window.begin());window.erase(window.begin());}if (mp.size() >= m){long long sum = accumulate(window.begin(), window.end(), 0LL);max_sum = max(max_sum, sum);}}return max_sum;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 为数组 nums 的长度。

空间复杂度：O(k)。哈希表的大小不会超过窗口长度，即 k。

这篇关于Leetcode2841. 几乎唯一子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---