LeetCode 2461: Maximum Sum of Distinct Subarrays With Length K (Sliding Window + Frequency Map)
LeetCode 2461Sliding WindowHash TableToday we solve LeetCode 2461 - Maximum Sum of Distinct Subarrays With Length K.
Source: https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/
English
Problem Summary
Given an integer array nums and integer k, find the maximum sum among all subarrays of length k where all elements are distinct. If no such window exists, return 0.
Key Insight
This is a fixed-size sliding window problem with an extra distinctness constraint. Maintain:
- window sum
- frequency map in current window
- the number of keys in the map (or map size)
A window is valid exactly when its length is k and distinct count is also k.
Brute Force and Limitations
Brute force checks every length-k subarray, recomputes sum and uniqueness each time. This leads to O(nk) time, too slow for large inputs.
Optimal Algorithm Steps (Sliding Window)
1) Expand right pointer and add nums[right] to sum + freq.
2) If window size exceeds k, remove nums[left], then advance left.
3) When window size is exactly k, check if freq.size() == k.
4) If valid, update answer with current sum.
Complexity Analysis
Time: O(n) average.
Space: O(k).
Common Pitfalls
- Forgetting to delete a key when its frequency drops to zero.
- Using int for sum (can overflow); use 64-bit type.
- Checking distinctness before shrinking oversized window.
- Returning negative sentinel instead of 0 when no valid window exists.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
java.util.Map freq = new java.util.HashMap<>();
long sum = 0L;
long ans = 0L;
int left = 0;
for (int right = 0; right < nums.length; right++) {
int x = nums[right];
sum += x;
freq.put(x, freq.getOrDefault(x, 0) + 1);
if (right - left + 1 > k) {
int y = nums[left++];
sum -= y;
int c = freq.get(y) - 1;
if (c == 0) freq.remove(y);
else freq.put(y, c);
}
if (right - left + 1 == k && freq.size() == k) {
ans = Math.max(ans, sum);
}
}
return ans;
}
} func maximumSubarraySum(nums []int, k int) int64 {
freq := make(map[int]int)
var sum int64 = 0
var ans int64 = 0
left := 0
for right := 0; right < len(nums); right++ {
x := nums[right]
sum += int64(x)
freq[x]++
if right-left+1 > k {
y := nums[left]
left++
sum -= int64(y)
freq[y]--
if freq[y] == 0 {
delete(freq, y)
}
}
if right-left+1 == k && len(freq) == k {
if sum > ans {
ans = sum
}
}
}
return ans
}class Solution {
public:
long long maximumSubarraySum(vector& nums, int k) {
unordered_map freq;
long long sum = 0, ans = 0;
int left = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
int x = nums[right];
sum += x;
++freq[x];
if (right - left + 1 > k) {
int y = nums[left++];
sum -= y;
if (--freq[y] == 0) freq.erase(y);
}
if (right - left + 1 == k && (int)freq.size() == k) {
ans = max(ans, sum);
}
}
return ans;
}
}; from collections import defaultdict
from typing import List
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
freq = defaultdict(int)
window_sum = 0
ans = 0
left = 0
for right, x in enumerate(nums):
window_sum += x
freq[x] += 1
if right - left + 1 > k:
y = nums[left]
left += 1
window_sum -= y
freq[y] -= 1
if freq[y] == 0:
del freq[y]
if right - left + 1 == k and len(freq) == k:
ans = max(ans, window_sum)
return ans/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumSubarraySum = function(nums, k) {
const freq = new Map();
let sum = 0;
let ans = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
const x = nums[right];
sum += x;
freq.set(x, (freq.get(x) || 0) + 1);
if (right - left + 1 > k) {
const y = nums[left++];
sum -= y;
const c = freq.get(y) - 1;
if (c === 0) freq.delete(y);
else freq.set(y, c);
}
if (right - left + 1 === k && freq.size === k) {
ans = Math.max(ans, sum);
}
}
return ans;
};中文
题目概述
给定整数数组 nums 和整数 k，需要在所有长度为 k 的子数组中，找出“元素互不相同”窗口的最大元素和。若不存在合法窗口，返回 0。
核心思路
这是“定长滑动窗口 + 去重约束”。窗口内维护三件事：
- 当前窗口元素和
- 频次哈希表
- 不同元素个数（即哈希表大小）
当窗口长度为 k 且 freq.size == k 时，窗口合法。
基线解法与不足
朴素做法是枚举每个长度为 k 的子数组，再分别判断是否去重并求和。总复杂度约为 O(nk)，在大数据下不够快。
最优算法步骤（滑动窗口）
1）右指针扩张，加入 nums[right]，更新 sum 与 freq。
2）若窗口长度超过 k，移除 nums[left] 并左移。
3）当窗口长度恰为 k 时，检查 freq.size == k。
4）若合法，用当前窗口和更新答案。
复杂度分析
时间复杂度：O(n)（均摊）。
空间复杂度：O(k)。
常见陷阱
- 频次降到 0 后忘记删键，导致 distinct 计数错误。
- 用 32 位整数存窗口和，可能溢出。
- 窗口超过 k 时未先收缩就判断合法性。
- 没有合法窗口时应返回 0，而不是未初始化值。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
java.util.Map freq = new java.util.HashMap<>();
long sum = 0L;
long ans = 0L;
int left = 0;
for (int right = 0; right < nums.length; right++) {
int x = nums[right];
sum += x;
freq.put(x, freq.getOrDefault(x, 0) + 1);
if (right - left + 1 > k) {
int y = nums[left++];
sum -= y;
int c = freq.get(y) - 1;
if (c == 0) freq.remove(y);
else freq.put(y, c);
}
if (right - left + 1 == k && freq.size() == k) {
ans = Math.max(ans, sum);
}
}
return ans;
}
} func maximumSubarraySum(nums []int, k int) int64 {
freq := make(map[int]int)
var sum int64 = 0
var ans int64 = 0
left := 0
for right := 0; right < len(nums); right++ {
x := nums[right]
sum += int64(x)
freq[x]++
if right-left+1 > k {
y := nums[left]
left++
sum -= int64(y)
freq[y]--
if freq[y] == 0 {
delete(freq, y)
}
}
if right-left+1 == k && len(freq) == k {
if sum > ans {
ans = sum
}
}
}
return ans
}class Solution {
public:
long long maximumSubarraySum(vector& nums, int k) {
unordered_map freq;
long long sum = 0, ans = 0;
int left = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
int x = nums[right];
sum += x;
++freq[x];
if (right - left + 1 > k) {
int y = nums[left++];
sum -= y;
if (--freq[y] == 0) freq.erase(y);
}
if (right - left + 1 == k && (int)freq.size() == k) {
ans = max(ans, sum);
}
}
return ans;
}
}; from collections import defaultdict
from typing import List
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
freq = defaultdict(int)
window_sum = 0
ans = 0
left = 0
for right, x in enumerate(nums):
window_sum += x
freq[x] += 1
if right - left + 1 > k:
y = nums[left]
left += 1
window_sum -= y
freq[y] -= 1
if freq[y] == 0:
del freq[y]
if right - left + 1 == k and len(freq) == k:
ans = max(ans, window_sum)
return ans/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumSubarraySum = function(nums, k) {
const freq = new Map();
let sum = 0;
let ans = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
const x = nums[right];
sum += x;
freq.set(x, (freq.get(x) || 0) + 1);
if (right - left + 1 > k) {
const y = nums[left++];
sum -= y;
const c = freq.get(y) - 1;
if (c === 0) freq.delete(y);
else freq.set(y, c);
}
if (right - left + 1 === k && freq.size === k) {
ans = Math.max(ans, sum);
}
}
return ans;
};
Comments