[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K

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

长度为 K 子数组中的最大和。

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

思路

思路是滑动窗口。这一题是滑动窗口，窗口尺寸固定为 K。这里我用 hashmap 记录每个不同元素及其出现次数。如果你是用 for 循环来维护窗口的尺寸的话（意思是右指针往前走一步，左指针立马也往前走一步），只能用 hashmap 做。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        long sum = 0L;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        long res = 0L;
        if (map.size() == k) {
            res = sum;
        }

        for (int i = k; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            sum += nums[i];
            sum -= nums[i - k];
            map.put(nums[i - k], map.get(nums[i - k]) - 1);
            if (map.get(nums[i - k]) == 0) {
                map.remove(nums[i - k]);
            }
            if (map.size() == k) {
                res = Math.max(res, sum);
            }
        }
        return res;
    }
}