Find X-Sum of All K-Long Subarrays II
You are given an array nums of n integers and two integers k and x.
The x-sum of an array is calculated by the following procedure:
- Count the occurrences of all elements in the array.
- Keep only the occurrences of the top
xmost frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent. - Calculate the sum of the resulting array.
Note that if an array has less than x distinct elements, its x-sum is the sum of the array.
Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].
Example 1
Input
nums = [1,1,2,2,3,4,2,3], k = 6, x = 2Output
[6,10,12]For the three length-6 subarrays, the kept elements are respectively 1 and 2, then 2 and 4, then 2 and 3, producing sums 6, 10, and 12.
Example 2
Input
nums = [3,8,7,8,7,5], k = 2, x = 2Output
[11,15,15,15,12]Since k == x, each answer is equal to the sum of the corresponding length-2 subarray.
Constraints
- nums.length == n
- 1 <= n <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= x <= k <= nums.length