LeetCode 2461. Maximum Sum of Distinct Subarrays With Length K

原题链接在这里：https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/

题目：

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

• The length of the subarray is k, and
• All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

题解：

Have a map to maintain the num and its frequency.

When a num's frequency changes from 0 to 1, then distinct count++.

When i >= k - 1, then we start to have subarray with length k.

If current distinct count == k, then all the numbers in subarray are distinct. Update the maximum result.

Move the walker, update sum and count.

Time Complexity: O(n). n = nums.length.

Space: O(k).

AC Java:

 1 class Solution {
 2     public long maximumSubarraySum(int[] nums, int k) {
 3         long res = 0;
 4         int n = nums.length;
 5         int count = 0;
 6         HashMap<Integer, Integer> hm = new HashMap<>();
 7         long sum = 0;
 8         for(int i = 0; i < n; i++){
 9             sum += nums[i];
10             hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
11             if(hm.get(nums[i]) == 1){
12                 count++;
13             }
14 
15             if(i >= k - 1){
16                 if(count == k){
17                     res = Math.max(res, sum);
18                 }
19 
20                 sum -= nums[i - k + 1];
21                 hm.put(nums[i - k + 1], hm.get(nums[i - k + 1]) - 1);
22                 if(hm.get(nums[i - k + 1]) == 0){
23                     count--;
24                 }
25             }
26         }
27 
28         return res;
29     }
30 }