LeetCode 3321: Find X-Sum of All K-Long Subarrays II
Problem Description
Explanation
To solve this problem, we can use a sliding window approach. We will maintain a frequency map of elements within the current window and update it as we slide the window. We will also maintain a priority queue to keep track of the top x most frequent elements within the window.
At each step, we will calculate the x-sum of the current window and store it in the result array.
The time complexity of this approach is O(n log x), where n is the length of the input array nums.
Solutions
import java.util.*;
class Solution {
public int[] findXSumOfAllKLongSubarraysII(int[] nums, int k, int x) {
int n = nums.length;
int[] answer = new int[n - k + 1];
Map<Integer, Integer> freqMap = new HashMap<>();
PriorityQueue<Integer> topX = new PriorityQueue<>((a, b) -> freqMap.get(a) == freqMap.get(b) ? b - a : freqMap.get(a) - freqMap.get(b));
for (int i = 0; i < k; i++) {
freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
}
for (int i = k; i <= n; i++) {
topX.clear();
topX.addAll(freqMap.keySet());
int sum = 0;
for (int j = 0; j < x && !topX.isEmpty(); j++) {
int num = topX.poll();
sum += num * freqMap.get(num);
}
answer[i - k] = sum;
if (i < n) {
freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
int removedElement = nums[i - k];
if (freqMap.get(removedElement) == 1) {
freqMap.remove(removedElement);
} else {
freqMap.put(removedElement, freqMap.get(removedElement) - 1);
}
}
}
return answer;
}
}Loading editor...