class Solution {
public:
long long maxSum(vector<int>& nums, int m, int k) {
}
};
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] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。
示例 3：
输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3 输出：0 解释：输入数组中不存在长度为k = 3的子数组含有至少m = 3个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。
提示：
1 <= nums.length <= 2 * 1041 <= m <= k <= nums.length1 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 76 ms, 内存消耗: 7.5 MB, 提交时间: 2023-09-04 09:53:07
func maxSum(nums []int, m, k int) (ans int64) {
sum := int64(0)
cnt := map[int]int{}
for _, x := range nums[:k-1] { // 先统计 k-1 个数
sum += int64(x)
cnt[x]++
}
for i, in := range nums[k-1:] {
sum += int64(in) // 再添加一个数就是 k 个数了
cnt[in]++
if len(cnt) >= m && sum > ans {
ans = sum
}
out := nums[i]
sum -= int64(out) // 下一个子数组不包含 out，移出窗口
cnt[out]--
if cnt[out] == 0 {
delete(cnt, out)
}
}
return
}
cpp 解法, 执行用时: 148 ms, 内存消耗: 63.4 MB, 提交时间: 2023-09-04 09:52:46
class Solution {
public:
long long maxSum(vector<int> &nums, int m, int k) {
long long ans = 0, sum = 0;
unordered_map<int, int> cnt;
for (int i = 0; i < k - 1; i++) { // 先统计 k-1 个数
sum += nums[i];
cnt[nums[i]]++;
}
for (int i = k - 1; i < nums.size(); i++) {
sum += nums[i]; // 再添加一个数就是 k 个数了
cnt[nums[i]]++;
if (cnt.size() >= m)
ans = max(ans, sum);
int out = nums[i - k + 1];
sum -= out; // 下一个子数组不包含 out，移出窗口
if (--cnt[out] == 0)
cnt.erase(out);
}
return ans;
}
};
java 解法, 执行用时: 45 ms, 内存消耗: 45.8 MB, 提交时间: 2023-09-04 09:52:00
class Solution {
public long maxSum(List<Integer> nums, int m, int k) {
var a = nums.stream().mapToInt(i -> i).toArray();
long ans = 0, sum = 0;
var cnt = new HashMap<Integer, Integer>();
for (int i = 0; i < k - 1; i++) { // 先统计 k-1 个数
sum += a[i];
cnt.merge(a[i], 1, Integer::sum); // cnt[a[i]]++
}
for (int i = k - 1; i < nums.size(); i++) {
sum += a[i]; // 再添加一个数就是 k 个数了
cnt.merge(a[i], 1, Integer::sum); // cnt[a[i]]++
if (cnt.size() >= m)
ans = Math.max(ans, sum);
int out = a[i - k + 1];
sum -= out; // 下一个子数组不包含 out，移出窗口
if (cnt.merge(out, -1, Integer::sum) == 0) // --cnt[out] == 0
cnt.remove(out);
}
return ans;
}
}
python3 解法, 执行用时: 292 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-04 09:51:44
# 滑动窗口，cnt维护窗口大小，sum维护窗口之和
class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
ans = 0
s = sum(nums[:k - 1]) # 先统计 k-1 个数
cnt = Counter(nums[:k - 1])
for out, in_ in zip(nums, nums[k - 1:]):
s += in_ # 再添加一个数就是 k 个数了
cnt[in_] += 1
if len(cnt) >= m:
ans = max(ans, s)
s -= out # 下一个子数组不包含 out，移出窗口
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out]
return ans