Maximum Sum of Distinct Subarrays With Length K
MediumArrayHash TableSliding Window
Solution
export function maximumSubarraySum(nums: number[], k: number): number {
const n = nums.length;
const counter = new Counter(nums.slice(0, k));
let start = 0;
let subarraySum = nums.slice(0, k).reduce((acc, num) => acc + num, 0);
let answer = counter.isDistinct ? subarraySum : 0;
for (let end = k; end < n; end++) {
counter.sub(nums[start]);
counter.add(nums[end]);
subarraySum += nums[end] - nums[start];
if (counter.isDistinct) {
answer = Math.max(answer, subarraySum);
}
start += 1;
}
return answer;
}
class Counter {
private totalCount: number;
private readonly map: Map<number, number>;
constructor(nums: number[] = []) {
this.map = new Map();
this.totalCount = 0;
nums.forEach((num) => {
this.add(num);
});
}
get(num: number): number {
return this.map.get(num) ?? 0;
}
add(num: number) {
this.totalCount += 1;
this.map.set(num, this.get(num) + 1);
}
sub(num: number) {
this.totalCount -= 1;
if (this.get(num) <= 1) {
this.map.delete(num);
} else {
this.map.set(num, this.get(num) - 1);
}
}
get isDistinct() {
return this.totalCount === this.map.size;
}
}
Complexity
- Time:
- Space: