Find X-Sum of All K-Long Subarrays I
EasyArrayHash TableSliding WindowHeap (Priority Queue)
Solution
export function findXSum(nums: number[], k: number, x: number): number[] {
const n = nums.length;
const counter = new Counter(nums.slice(0, k));
const answer = [counter.xSum(x)];
for (let i = k; i < n; i++) {
counter.sub(nums[i - k]);
counter.add(nums[i]);
answer.push(counter.xSum(x));
}
return answer;
}
class Counter {
private readonly map: Map<number, number>;
constructor(nums: number[]) {
this.map = new Map();
nums.forEach((num) => {
this.add(num);
});
}
get(key: number): number {
return this.map.get(key) ?? 0;
}
add(key: number) {
return this.map.set(key, this.get(key) + 1);
}
sub(key: number) {
return this.map.set(key, this.get(key) - 1);
}
xSum(x: number) {
return [...this.map.entries()]
.sort((a, b) => (a[1] !== b[1] ? b[1] - a[1] : b[0] - a[0]))
.slice(0, x)
.reduce((prev, curr) => prev + curr[0] * curr[1], 0);
}
}
Complexity
- Time:
O(N*KlogK)
- Space:
O(N)